ハミルトン閉路(読み)はみるとんへいろ

世界大百科事典内のハミルトン閉路の言及

【アルゴリズム】より


[非決定性アルゴリズム]
 巡回セールスマン問題に〈すべての都市をちょうど1回ずつ通過し,出発点に戻る〉という条件を追加すると,解が存在しない場合も出てくる。しかしこの条件をみたす経路(いわゆる〈ハミルトン閉路〉)が存在するかどうかは,次のような方針で判定できる。まず最初は指定された出発点にいるとして,次の作業(ア)を繰り返す。…

【数学パズル】より

…図17‐aはアーレンスW.Ahrens著の《数学遊戯》第2巻(1918)にある問題で,かなり複雑そうに見えるけれども,A点とB点だけが奇数の点であることを確認すれば図17‐bのような解が簡単に得られる。一筆書きと似たトポロジーパズルにハミルトン閉路の問題がある。W.R.ハミルトンが考えたもので,その結果を1859年に報告している。…

※「ハミルトン閉路」について言及している用語解説の一部を掲載しています。

出典|株式会社平凡社世界大百科事典 第2版について | 情報

関連語をあわせて調べる

今日のキーワード

KPI

KPIとはkey performance indicator の略で、企業目標の達成度を評価するための主要業績評価指標のことをいう。...

続きを読む

コトバンク for iPhone

コトバンク for Android