TSP-Solver
#addsub
G-Code弄りにおいて、ルートを最適化したい
Lin-Kerningham法
code:ln-solver.ts
/**
* Stroke: ペンプロッターの「始点→終点」の2次元座標
*/
type Stroke = [
x1: number, y1: number,
x2: number, y2: number
];
/**
* Node: どのストロークを、正方向(始点→終点) or 逆方向(終点→始点)で描くか
*/
type Node = {
strokeIndex: number; // 何番目のストロークか
direction: 'forward' | 'backward';
};
/**
* Nodeから「描き終わりの座標」を取り出す
*/
function getEndPoint(strokes: Stroke[], node: Node): number, number {
const stroke = strokesnode.strokeIndex;
return node.direction === 'forward' ? stroke1 : stroke0;
}
/**
* Nodeから「描き始めの座標」を取り出す
*/
function getStartPoint(strokes: Stroke[], node: Node): number, number {
const stroke = strokesnode.strokeIndex;
return node.direction === 'forward' ? stroke0 : stroke1;
}
/**
* 2点間の距離
*/
function distance(a: number, number, b: number, number): number {
const dx = a0 - b0;
const dy = a1 - b1;
return Math.sqrt(dx * dx + dy * dy);
}
/**
* 連続するNodeの順序から経路の「移動コスト合計」を計算する
* ペンを上げて移動する距離だけを加算する想定。
* （ストロークを描く間のコストを考えたいなら、始点→終点の距離を足すなど工夫する）
*/
function totalRouteDistance(strokes: Stroke[], route: Node[]): number {
let sum = 0;
for (let i = 0; i < route.length - 1; i++) {
const endPos = getEndPoint(strokes, routei);
const startPos = getStartPoint(strokes, routei + 1);
sum += distance(endPos, startPos);
}
return sum;
}
/**
* ノード列のうち、区間 i, j を反転（2-optの一種）
* 本当はストロークの向きも入れ替えたい場合があるが、ここでは「ノードの順序のみ」をひっくり返す簡易例
*/
function twoOptSwap(route: Node[], i: number, j: number): Node[] {
const newRoute = route.slice();
// 区間 i～j を反転
while (i < j) {
[newRoutei, newRoutej] = [newRoutej, newRoutei];
i++;
j--;
}
return newRoute;
}
/**
* Lin-Kernighanの「ほんの入り口」を模した簡易例
* - 本格的には複数段階のk-optを再帰的に探すなど実装が大きくなる
* - ここでは「2-optを段階的に拡張し、改善があれば続行」という流れのイメージ
*/
function linKernighan(
strokes: Stroke[],
initialRoute: Node[],
maxIterations: number
): Node[] {
let bestRoute = initialRoute.slice();
let bestDist = totalRouteDistance(strokes, bestRoute);
// ここでは「2-optを改良する過程で少し拡張する」程度の擬似的な例
// 実際のLKでは「k本の辺を切り替えながら改良があれば継続」など
for (let iter = 0; iter < maxIterations; iter++) {
let improved = false;
// シンプルに全ペア (i, j) を走査（Nが大きいと厳しいので本来は絞り込み必須）
for (let i = 0; i < bestRoute.length - 2; i++) {
for (let j = i + 2; j < bestRoute.length - 1; j++) {
const newRoute = twoOptSwap(bestRoute, i + 1, j);
const newDist = totalRouteDistance(strokes, newRoute);
if (newDist < bestDist) {
bestRoute = newRoute;
bestDist = newDist;
improved = true;
break; // 外ループに戻って再探索
}
}
if (improved) break;
}
// 2-optでも改善が見つからなかった → 打ち切り
if (!improved) break;
// 本格的にはさらに「次のk本目を交換してみる」などを繰り返し探す
// ただしここでは省略
}
return bestRoute;
}
// === 以下、使い方サンプル ===
function solveStrokes(strokes: Stroke[]): Node[] {
// 例: 全てのストロークを正方向に描く初期解を作り、単純に並べる
const initialRoute: Node[] = strokes.map((_, idx) => ({
strokeIndex: idx,
direction: 'forward',
}));
// Lin-Kernighan的アルゴリズムで順序を改善
const improvedRoute = linKernighan(strokes, initialRoute, 200);
return improvedRoute;
}
// 動作例
function main() {
const strokes: Stroke[] = [
0, 0], [10, 10,
10, 10], [20, 5,
20, 5], [15, 0,
// ... 以下多数
];
const route = solveStrokes(strokes);
console.log('Best route:', route);
}