MathematicaのFindShortestTourのバグ

先日CodeIQで、巡回セールスパースン問題を出題しました。

Mathematicaには、指定した点をすべて通る最短の巡回路を求める関数 FindShortestTour があるので、これを使えば簡単なはずでしたが、実はそこにはトラップがあったかもしれません。

追記:問題は3つありますが、Mathematica 10.4.1, 11.2で未解決なのは3番目のみです。

問題1(10.0.2 for Windowsで解決)

Mathematica 10.0.1 for Windowsでは、{{6, 2}, {4, 6}, {3, 4}, {6, 7}}という4点を通る最短巡回路を求められませんでした。

問題2(10.0 for Linux ARM (32-bit) (August 4, 2014)で解決)

10.0 for Linux ARM (32-bit) (January 29, 2014)の FindShortestTour は、仕様がマニュアルと違っていました。

pts = {{1, 1}, {1, 2}, {1, 3}, {1, 4}, {1, 5}, {2, 1}, {2, 3}, {2, 5}, {3, 1}, {3, 2}, {3, 4}, {3, 5}, {4, 1}, {4, 3}, {4, 5}, {5, 1}, {5, 2}, {5, 3}, {5, 4}};
FindShortestTour[%]

マニュアルによれば、巡回路の最初と最後は同じ(この例では1)はずなのですが、ここで得られる結果は「{14 + 5 Sqrt[2], {1, 2, 7, 3, 4, 5, 8, 12, 11, 15, 19, 14, 18, 17, 16, 13, 9, 10, 6}}」で、仕様とは違っていました。

問題3(10.4.1, 11.2, 11.3 for Windowsで未解決)

1分待っても結果が返ってこない場合があります(Core i7-4930K)。(Wolfram/Alphaでは計算できたこともある

FindShortestTour[{{0, 0}, {1, 0}, {0, 1}, {1, 1}, {0, 536870913}}]

浮動小数点で近似値だけでも・・・と思っても、やはりダメな場合があります(カーネルが落ちます)。

FindShortestTour[{{1., 0}, {0, 1}, {6421482390570520, 4284269602932036}, {239817909316376, 7744567430237013}, {2528914430818969, 5966759469595075}}]

マニュアルでは見つけられませんでしたが、「Method -> "IntegerLinearProgramming"」を付けておくとうまくいくと、サポートから教えてもらいましたが、計算はできても結果が正しくない場合があります。(この例でオプションを外すとカーネルが落ちます。)

cities = {
 {12581820340729273, 10017935966728831},
 {12754218452664193, 14539145895971681},
 {14822745302277607, 14565274414261943},
 {11873373307008371, 9781014188323403},
 {16116822349097741, 15873203518310113},
 {12701673778654019, 11291535066125623},
 {9392560345300883, 14963106019249771},
 {11529795864075473, 17759422650313613},
 {9007199254742147, 18014398509483463},
 {9007199254742149, 18014398509483461}};
FindShortestTour[cities, Method -> "IntegerLinearProgramming"]

一部のバージョンでは、巡回路{1, 4, 7, 9, 10, 8, 5, 3, 2, 6, 1}が得られますが、正解は{1, 4, 7, 10, 9, 8, 5, 3, 2, 6, 1}です。

何も気にせず使えるようになるにはまだ時間がかかりそうです。

Unicodeのすべての文字を1回ずつ使って絵を描く

文字の並びで表現された絵は一般にアスキーアートと呼ばれます。その名前からは、使える文字がASCII文字に制限されているように思えますが、実際はそうではなく、なんでもありです。「MS Pゴシック」に含まれる文字を使うのが伝統でしょうか。

先日数えてみたように、Unicode 6.0にはGraphic Characterが109242個あります(参照:Unicodeのすべての文字を1ページで)。使える文字をここまで広げると、いわゆるアスキーアートのように文字の形を利用するのではなく、文字の濃さを利用して絵を描けます。(Graphic Charactersに印刷できない文字も含まれていることは、ここでは無視します。)

せっかくこれだけの文字があるので、それぞれの文字は1回しか使えないという制約を入れましょう。正方形のキャンバスなら、331 × 331のグリッド上に文字を並べることになります(331 x 331 = 109561は109242以上の最小の平方数)。ちょっと文字が足りないので、その分は半角スペースで補うことにします(109561 – 109242 = 319個)。

こんな絵が描けます(クリックで拡大、PDF 23MB)。

Adobe-Japan1-6のすべてのグリフを1ページで

この記事で作るもの:Adobe-Japan1-6の全23058グリフを1ページで (PDF, 5MB)

Unicodeの文字の一覧を作ったのに続いて、Adobe-Japan1-6のグリフの一覧を作ります。自分で作らなくてもAdobe-Japan1のグリフ一覧は、

しかし、自分で作れるようになっていれば、全グリフを1ページにといった、自分の好きなレイアウトの一覧表が作れます。

改訂版が出るたびに買っている奥村晴彦, 黒木裕介『LaTeX2ε美文書作成入門』(技術評論社, 第6版, 2013)にも、判型が変わった頃から“Adobe-Japan1全グリフ”が掲載されているのですが、書体が小塚明朝ではなくヒラギノ明朝なので、ここでの目的には適しません。以前書いたように、小塚明朝では区別され、ヒラギノ明朝では区別されない漢字のペアがあるので、ヒラギノ明朝では全グリフにはならないのです。『基本日本語活字見本集成』の著者の一人である小形克宏さんも、ブログで次のように書いています。

このページをより一般的なヒラギノ明朝で組むという話が出たとき、ぼくはかなり強く小塚明朝でなければ信頼性を担保できないことを主張しました。仮にヒラギノ明朝でAdobe-Japan1-5を表しても、それはヒラギノとしての実装解釈を示したにすぎず、仕様制定者の本来の意図が見えなくなってしまいます。Adobe-Japan1は文字コード規格ではなく、あくまでも「グリフ」セットなのですから、小塚明朝のタイプフェイス・デザインを前提とするのは自明の理であり、その意味で小塚明朝で掲載されたことは至極当然と言えるでしょう。『基本日本語活字見本集成本OpenType版』のこと (1)

というわけで、小塚明朝で作ります。

小塚明朝とTeXLiveがインストールされた環境で、「kanji-config-updmap kozuka-pr6n」として小塚明朝を埋め込めるようにします。Adobe-Japan1-6のCIDは、0から23057まで、間を空けずに使われているようなので、単純な繰り返しをするTeXファイルで一覧を作れます。こうして作った一覧表が冒頭のPDFファイルです(改行の制御に不満があります@doraTeXさんのコードを参考に修正しました)。

Unicodeのすべての文字を1ページで

この記事で作るもの:Unicode 6.0のすべての文字を1ページで (PDF, 23MB)

4327377368ヨハネス・ベルガーハウゼン, シリ・ポアランガン『世界の文字と記号の大図鑑 ー Unicode 6.0の全グリフ』(研究社, 2014)の著者はUnicode 6.0の全109242文字2時間30分かけて見るビデオの作者ですか。今度は1024ページの書籍。「Decodeunicode」で画像検索すると原著が出てきますが、楽しみですね。(追記:世界の文字と記号の大図鑑

「Unicodeのすべての文字を印刷した本って、前にもなかったっけ?」と思って本棚を探したのですが、勘違いでした。

0321480910頭に浮かんだのはThe Unicode Consortium『The Unicode Standard, Version 5.0』(Addison-Wesley Professional, 2006)(文献リストあり、索引なし)だったのですが、この本は、(1) The Unicode Standard、(2) Code Charts (PDF)から漢字を除いたもの、(3) Han Radical-Stroke Index (PDF)という構成でした。つまり、漢字はコードポイント順に一つずつではなく、Han Radical-Stroke Indexという形で掲載されているだけでした。

Unicode 5.0より後は、紙媒体ではないようですが、たとえば6.0について同じことをするなら、 (1) The Unicode Standard (PDF)、(2) Code Charts (PDF)、(3) Han Radical-Stroke Index (PDF)を使うことになるのでしょう。(Code Chartsには漢字も含まれているので、「文字の一覧(番号順)」が欲しいだけならCode Chartsだけで十分です。)

これらの資料もいいのですが、こういうのは、自分でもちょっとやってみたいところです。例えば、Unicodeの全文字を1ページに、なんてことも、自分で作れるようになればできます。

というわけで、必要なデータをEnumerated Versions of The Unicode Standardから探して作ろうとしたら、これがなかなか面倒でした。

Unicode 6.0の全文字は、UnicodeData.txtに載っているはずですが、この第1列をHTMLの数値文字参照に置き換えるだけでは終わりません。

UnicodeData.txtには、CJK統合漢字など、1行1文字になっていない部分があります。それを補うのは面倒なので、Unicode 5.1以降で導入されたUnicode Character
Database in XML
を使うことにします。このXMLファイルは、char要素1個が1文字に対応します。

XMLファイルには、印刷できない文字?も含まれているので、それを除外しなければなりません。Unicode 6.0のコードポイントは109449個ありますが、そのうちGraphic Characterは109242個です(参照)。『世界の文字と記号の大図鑑』の109242文字というのはこれのことなのでしょう。Graphic Characterの定義General_Category ValuesThe Unicode Standard Chapter 2 General Structureの「Table 2-3. Types of Code Points」を見ると、char要素のgc属性値がCから始まるものとZl, Zpになっているものは除外しなければならないことがわかります。(異体字セレクタのような、明らかに印刷不能な文字が残るのですが、とりあえずはそのままにします。それを使う異体字もここでは数えません。)

というわけで、ちょっとスクリプトを書いて、Unicode 6.0の文字の一覧を作ります。

こんなHTMLファイルです。このファイルは、Unicodeの文字を数値文字参照で書いてあるだけのものなので、文字を実際に表示できるかどうかは環境によります。Noto花園明朝などを入れた環境で、Firefox 31とChrome 36を試したところ、FirefoxはUnicode 6.0のすべての字形を表示できたようですが、Chromeはぜんぜんだめでした(目視以外の確認法がわかりません)。

Windows上のFirefoxでAdobe PDFに印刷した結果が冒頭のPDFファイルです。

完成に必要な無料フォントを列挙する(あるいはもっとよい方法の提案)という自由研究を、どこかの小学生がやってくれることを期待します。

関連:Unicodeのすべての文字を1回ずつ使って絵を描く

追記:The Unicode Map Projectがすばらしいです。

MathematicaのClusteringComponentsの困ったところ

Mathematica 9.0, 10.0, 10.1, 10.2, 10.3, 10.4.1, 11.2, 11.3 for Microsoft Windows (64-bit)と10.0.0 for Linux ARM (32-bit)でのことです。

Mathematicaには、階層的クラスタリングができる関数が3つ用意されています。FindClustersAgglomerateClusteringComponentsです。

FindClustersにはバグがありました。(FindClustersのバグは11で解決)

Agglomerateにはバグがあります。

バグではありませんが、ClusteringComponentsにも困ったところがあります。データをn個のクラスタに分けたいと思ってClusteringComponents[array,n]としても、できるクラスタがnより少ないことがあるのです。マニュアルには「最高でn個のクラスタを求める」とあるので、nより少ないのはバグでは無いのですが、ちょうどn個のクラスタを作りたいときに使えないのは困ります。

次のコードで再現できます。

data = Import["https://gist.github.com/taroyabuki/4996086/raw/be3b2d537a51b803790fa1149cc714663a8b6ee9/clustering_test_data2.csv"];

Length[Union[ClusteringComponents[data, 13, 1, DistanceFunction -> EuclideanDistance, Method -> "Optimize"]]]
(* 12 *)

13個のクラスタを作りたかったのですが、できたクラスタは12個でした。

データをシャッフルしてからならうまくいきます。

Length[Union[ClusteringComponents[RandomSample@data, 13, 1, DistanceFunction -> EuclideanDistance, Method -> "Optimize"]]]
(* 13 *)

というわけで、階層的クラスタリングをしたいときはRを使うのがよさそうです(参考)。