最短距離を求めるプログラム

　　最短距離を求めるプログラム ななえ 2004/06/05 22:26:32 
　　├!このプログラムではまず最初に始点を決め(... 大久保 2004/06/06 00:05:18 
　　├探索途中の仮の最短コースを記録するための... 白石　和夫 2004/06/06 06:44:24 
　　│└N個の点の座標を入力する部分は， 白石　和夫 2004/06/06 08:12:25 
　　└Nはいくつくらいまで想定すれば良いのでしょ... 哲 2004/06/09 15:12:06 
　　　└だいたい10個くらいです。よろしくお願いし... ななえ 2004/06/15 01:48:50 
　　　　└並べ替えが大変でしたが一応できました。バ... 哲 2004/06/15 21:15:17 
　　　　　└一部消し忘れが在りました。 哲 2004/06/16 09:45:30 
　　　　　　└すみません。間違いがありました。 哲 2004/06/17 21:05:41

　　最短距離を求めるプログラム ななえ 2004/06/05 22:26:32  ツリーへ

最短距離を求めるプログラム 返事を書く

ななえ 2004/06/05 22:26:32

はじめまして。
N個の点の座標を入力して一筆書きで各点を通り最初の点に最短距離で戻ってくるプログラムを作りたいのですが・・・
どなたか教えてください(>＿<)

　　├!このプログラムではまず最初に始点を決め(... 大久保 2004/06/06 00:05:18  ツリーへ

Re: 最短距離を求めるプログラム 返事を書く

大久保 2004/06/06 00:05:18

!このプログラムではまず最初に始点を決め(赤い点)、そこから
!一番近い所にある点を結びます。つぎにその点から一番近い所にある点を結びます。
!それを繰り返して、{最後に始点と線をつなぎます}。
!なのでひょっとすると、{}部分のせいで最短コースが得られないかも知れません。
randomize
let n=20
dim px(n)
dim py(n)
dim D(n)
set window 0,1,0,1
for i=1 to n
let px(i)=rnd
let py(i)=rnd
if i=1 then set point color 4 else set point color 1
plot points:px(i),py(i)
next i
plot lines:px(1),py(1);

let d(1)=1
let nn=1
for j=1 to n
let distance=maxnum
for i=2 to n
if d(i)=1 then goto 100
let dis=sqr((px(nn)-px(i))^2+(py(nn)-py(i))^2)
if distance>dis then
let distance=dis
let nm=i
end if
100 next i
let d(nm)=1
let nn=nm
plot lines:px(nm),py(nm);
next j
plot lines:px(nm),py(nm);px(1),py(1)
end

　　├探索途中の仮の最短コースを記録するための... 白石　和夫 2004/06/06 06:44:24  ツリーへ

Re: 最短距離を求めるプログラム 返事を書く

白石　和夫 2004/06/06 06:44:24

探索途中の仮の最短コースを記録するための配列s(N)と仮の最短距離を記録する変数tと用意しておきます。
N個の点の順列をすべて生成して，各順列について距離の和を求め，その時点での最短ルートと最短距離を更新していきます。
順列すべてについて処理が終われば，その時点での最短ルートが本当の最短ルートです。
順列すべてを生成する方法は，何通りかありますが，初心者向きの方法を「数学とコンピュータ１」（森北出版）に解説してあるので参照してください。

　　│└N個の点の座標を入力する部分は， 白石　和夫 2004/06/06 08:12:25  ツリーへ

Re: 探索途中の仮の最短コースを記録するための... 返事を書く

白石　和夫 2004/06/06 08:12:25

N個の点の座標を入力する部分は，
100 INPUT n
110 DIM x(n),y(n)
120 FOR i=1 TO n
130 GET POINT: x(i),y(i)
140 NEXT i
です。

　　└Nはいくつくらいまで想定すれば良いのでしょ... 哲 2004/06/09 15:12:06  ツリーへ

Re: 最短距離を求めるプログラム 返事を書く

哲 2004/06/09 15:12:06

Nはいくつくらいまで想定すれば良いのでしょうか？
１０個で３６万以上の方法を計算することになって、
時間も掛かりますし難しくなりそうなのですが、Nの上限が決まっていれば考え易いのですが？

　　　└だいたい10個くらいです。よろしくお願いし... ななえ 2004/06/15 01:48:50  ツリーへ

Re: Nはいくつくらいまで想定すれば良いのでしょ... 返事を書く

ななえ 2004/06/15 01:48:50

だいたい10個くらいです。よろしくお願いします！

　　　　└並べ替えが大変でしたが一応できました。バ... 哲 2004/06/15 21:15:17  ツリーへ

Re: だいたい10個くらいです。よろしくお願いし... 返事を書く

哲 2004/06/15 21:15:17

並べ替えが大変でしたが一応できました。バグが在るかもしれません。

!*** N個の点を最短で結ぶプログラム ***
!　　順$は2-9を順に並べ替えた文字列：順$(2)は計算に使う文字列
!　　保存の必要に応じて順$(3),順$(4),・・・を作成
SET ECHO "OFF"

!点の入力
INPUT PROMPT "点の数(９以下)？":n
DIM x(n),y(n),順$(n),桁(9)
FOR i=1 TO n
　 INPUT PROMPT "点の座標を入力 x,y": x(i),y(i)
　 PRINT "n=";i;"　";x(i);",";y(i)
NEXT i

!最初の文字列　順$(1)を作成
LET 順$(1)="23456789"
LET 順$(1)=順$(1)(1:n-1)

LET　N0=FACT(n-1)　　　!並べ替えの総数
LET　順$(2)=順$(1)
LET i=1

!全ての並べ替えで計算
DO WHILE　i<=N0
　 CALL 計算
　 PRINT "1" & 順$(2) & "1",計　　　!並べ替えの表示
　 CALL 次順
　 LET　i=i+1
LOOP

PRINT "答え　　";"1" & 順min$ & "1"
IF 順next$<>"" THEN PRINT "答え２　";"1" & 順next$ & "1"

SUB 計算　!並べ替えた点を結ぶ線の計算
　 LET 計=0
　 LET　k0=1
　 FOR j=1 TO n-1
　　　LET　k=VAL(順$(2)(j:j))
　　　LET　計=計+(x(k)-x(k0))^2+(y(k)-y(k0))^2
　　　LET　k0=k
　 NEXT j
　 LET　計=計+(x(1)-x(k))^2+(y(1)-y(k))^2
　 IF i=1 THEN
　　　LET　最短=計
　　　LET　順min$=順$(2)
　 ELSE
　　　CALL 保存
　 END IF
END SUB

SUB 保存
　 LET 逆順$=""
　 FOR c=(n-1) TO 1 STEP -1
　　　LET　逆順$=逆順$ & MID$(順$(2),c,1)
　 NEXT c
　 IF 計<最短　THEN
　　　LET　最短=計
　　　LET　順min$=順$(2)
　 ELSEIF 計=最短 AND 逆順$<>順min$ THEN
　　　LET　順next$=順$(2)
　 ELSE
　 END IF
END SUB

SUB 次順
　 IF MOD(i,2)<>0 THEN
　　　CALL 移動(2)
　 ELSEIF MOD(i,40320)=0 THEN
　　　CALL 移動(9)
　 ELSEIF MOD(i,5040)=0 THEN
　　　CALL 移動(8)
　 ELSEIF MOD(i,720)=0 THEN
　　　CALL 移動(7)
　 ELSEIF MOD(i,120)=0 THEN
　　　CALL 移動(6)
　 ELSEIF MOD(i,24)=0 THEN
　　　CALL 移動(5)
　 ELSEIF MOD(i,6)=0 THEN
　　　CALL 移動(4)
　 ELSE
　　　CALL 移動(3)
　 END IF
END SUB

SUB 移動(桁)
　 IF 桁=2 THEN
　　　LET　順$(2)=MID$(順$(2),2,1) & MID$(順$(2),1,1) & MID$(順$(2),3,n-1)
　 ELSEIF　順$(桁)="" THEN
　　　LET　順$(桁)=MID$(順$(1),桁,1) & MID$(順$(1),1,桁-1) & MID$(順$(1),桁+1,n-1)
　　　LET　順$(2)=順$(桁)
　　　LET　c=3
　　　DO WHILE c<桁
　　　　 LET　順$(c)=順$(桁)
　　　　 LET　c=c+1
　　　LOOP
　 ELSE
　　　LET　順$(桁)=MID$(順$(桁),桁,1) & MID$(順$(桁),1,桁-1) & MID$(順$(桁),桁+1,n-1)
　　　LET　順$(2)=順$(桁)
　　　LET　c=3
　　　DO WHILE c<桁
　　　　 LET　順$(c)=順$(桁)
　　　　 LET　c=c+1
　　　LOOP
　 END IF
END SUB

END

　　　　　└一部消し忘れが在りました。 哲 2004/06/16 09:45:30  ツリーへ

Re: 並べ替えが大変でしたが一応できました。バ... 返事を書く

哲 2004/06/16 09:45:30

一部消し忘れが在りました。

!点の入力　の２行目最後の　,桁(9)
を消してください。

　　　　　　└すみません。間違いがありました。 哲 2004/06/17 21:05:41  ツリーへ

Re: 一部消し忘れが在りました。 返事を書く

哲 2004/06/17 21:05:41

すみません。間違いがありました。
SUB 計算部分を差し替えてください。

SUB 計算 !並べ替えた点を結ぶ線の計算
LET 計=0
LET k0=1
FOR j=1 TO n-1
LET k=VAL(順$(2)(j:j))
LET 計=計+SQR((x(k)-x(k0))^2+(y(k)-y(k0))^2)
LET k0=k
NEXT j
LET 計=計+SQR((x(1)-x(k))^2+(y(1)-y(k))^2)
IF i=1 THEN
LET 最短=計
LET 順min$=順$(2)
ELSE
CALL 保存
END IF
END SUB

インデックスへ EXIT
新規発言を反映させるにはブラウザの更新ボタンを押してください。

最短距離を求めるプログラム	返事を書く
ななえ 2004/06/05 22:26:32
はじめまして。 N個の点の座標を入力して一筆書きで各点を通り最初の点に最短距離で戻ってくるプログラムを作りたいのですが・・・どなたか教えてください(>＿<)

Re: 最短距離を求めるプログラム	返事を書く
大久保 2004/06/06 00:05:18
!このプログラムではまず最初に始点を決め(赤い点)、そこから !一番近い所にある点を結びます。つぎにその点から一番近い所にある点を結びます。 !それを繰り返して、{最後に始点と線をつなぎます}。 !なのでひょっとすると、{}部分のせいで最短コースが得られないかも知れません。 randomize let n=20 dim px(n) dim py(n) dim D(n) set window 0,1,0,1 for i=1 to n let px(i)=rnd let py(i)=rnd if i=1 then set point color 4 else set point color 1 plot points:px(i),py(i) next i plot lines:px(1),py(1); let d(1)=1 let nn=1 for j=1 to n let distance=maxnum for i=2 to n if d(i)=1 then goto 100 let dis=sqr((px(nn)-px(i))^2+(py(nn)-py(i))^2) if distance>dis then let distance=dis let nm=i end if 100 next i let d(nm)=1 let nn=nm plot lines:px(nm),py(nm); next j plot lines:px(nm),py(nm);px(1),py(1) end

Re: 最短距離を求めるプログラム	返事を書く
白石　和夫 2004/06/06 06:44:24
探索途中の仮の最短コースを記録するための配列s(N)と仮の最短距離を記録する変数tと用意しておきます。 N個の点の順列をすべて生成して，各順列について距離の和を求め，その時点での最短ルートと最短距離を更新していきます。順列すべてについて処理が終われば，その時点での最短ルートが本当の最短ルートです。順列すべてを生成する方法は，何通りかありますが，初心者向きの方法を「数学とコンピュータ１」（森北出版）に解説してあるので参照してください。

Re: 探索途中の仮の最短コースを記録するための...	返事を書く
白石　和夫 2004/06/06 08:12:25
N個の点の座標を入力する部分は， 100 INPUT n 110 DIM x(n),y(n) 120 FOR i=1 TO n 130 GET POINT: x(i),y(i) 140 NEXT i です。

Re: 最短距離を求めるプログラム	返事を書く
哲 2004/06/09 15:12:06
Nはいくつくらいまで想定すれば良いのでしょうか？１０個で３６万以上の方法を計算することになって、時間も掛かりますし難しくなりそうなのですが、Nの上限が決まっていれば考え易いのですが？

Re: Nはいくつくらいまで想定すれば良いのでしょ...	返事を書く
ななえ 2004/06/15 01:48:50
だいたい10個くらいです。よろしくお願いします！

Re: だいたい10個くらいです。よろしくお願いし...	返事を書く
哲 2004/06/15 21:15:17
並べ替えが大変でしたが一応できました。バグが在るかもしれません。 !* N個の点を最短で結ぶプログラム * !　　順$は2-9を順に並べ替えた文字列：順$(2)は計算に使う文字列 !　　保存の必要に応じて順$(3),順$(4),・・・を作成 SET ECHO "OFF" !点の入力 INPUT PROMPT "点の数(９以下)？":n DIM x(n),y(n),順$(n),桁(9) FOR i=1 TO n 　 INPUT PROMPT "点の座標を入力 x,y": x(i),y(i) 　 PRINT "n=";i;"　";x(i);",";y(i) NEXT i !最初の文字列　順$(1)を作成 LET 順$(1)="23456789" LET 順$(1)=順$(1)(1:n-1) LET　N0=FACT(n-1)　　　!並べ替えの総数 LET　順$(2)=順$(1) LET i=1 !全ての並べ替えで計算 DO WHILE　i<=N0 　 CALL 計算　 PRINT "1" & 順$(2) & "1",計　　　!並べ替えの表示　 CALL 次順　 LET　i=i+1 LOOP PRINT "答え　　";"1" & 順min$ & "1" IF 順next$<>"" THEN PRINT "答え２　";"1" & 順next$ & "1" SUB 計算　!並べ替えた点を結ぶ線の計算　 LET 計=0 　 LET　k0=1 　 FOR j=1 TO n-1 　　　LET　k=VAL(順$(2)(j:j)) 　　　LET　計=計+(x(k)-x(k0))^2+(y(k)-y(k0))^2 　　　LET　k0=k 　 NEXT j 　 LET　計=計+(x(1)-x(k))^2+(y(1)-y(k))^2 　 IF i=1 THEN 　　　LET　最短=計　　　LET　順min$=順$(2) 　 ELSE 　　　CALL 保存　 END IF END SUB SUB 保存　 LET 逆順$="" 　 FOR c=(n-1) TO 1 STEP -1 　　　LET　逆順$=逆順$ & MID$(順$(2),c,1) 　 NEXT c 　 IF 計<最短　THEN 　　　LET　最短=計　　　LET　順min$=順$(2) 　 ELSEIF 計=最短 AND 逆順$<>順min$ THEN 　　　LET　順next$=順$(2) 　 ELSE 　 END IF END SUB SUB 次順　 IF MOD(i,2)<>0 THEN 　　　CALL 移動(2) 　 ELSEIF MOD(i,40320)=0 THEN 　　　CALL 移動(9) 　 ELSEIF MOD(i,5040)=0 THEN 　　　CALL 移動(8) 　 ELSEIF MOD(i,720)=0 THEN 　　　CALL 移動(7) 　 ELSEIF MOD(i,120)=0 THEN 　　　CALL 移動(6) 　 ELSEIF MOD(i,24)=0 THEN 　　　CALL 移動(5) 　 ELSEIF MOD(i,6)=0 THEN 　　　CALL 移動(4) 　 ELSE 　　　CALL 移動(3) 　 END IF END SUB SUB 移動(桁) 　 IF 桁=2 THEN 　　　LET　順$(2)=MID$(順$(2),2,1) & MID$(順$(2),1,1) & MID$(順$(2),3,n-1) 　 ELSEIF　順$(桁)="" THEN 　　　LET　順$(桁)=MID$(順$(1),桁,1) & MID$(順$(1),1,桁-1) & MID$(順$(1),桁+1,n-1) 　　　LET　順$(2)=順$(桁) 　　　LET　c=3 　　　DO WHILE c<桁　　　　 LET　順$(c)=順$(桁) 　　　　 LET　c=c+1 　　　LOOP 　 ELSE 　　　LET　順$(桁)=MID$(順$(桁),桁,1) & MID$(順$(桁),1,桁-1) & MID$(順$(桁),桁+1,n-1) 　　　LET　順$(2)=順$(桁) 　　　LET　c=3 　　　DO WHILE c<桁　　　　 LET　順$(c)=順$(桁) 　　　　 LET　c=c+1 　　　LOOP 　 END IF END SUB END

Re: 並べ替えが大変でしたが一応できました。バ...	返事を書く
哲 2004/06/16 09:45:30
一部消し忘れが在りました。 !点の入力　の２行目最後の　,桁(9) を消してください。

Re: 一部消し忘れが在りました。	返事を書く
哲 2004/06/17 21:05:41
すみません。間違いがありました。 SUB 計算部分を差し替えてください。 SUB 計算 !並べ替えた点を結ぶ線の計算 LET 計=0 LET k0=1 FOR j=1 TO n-1 LET k=VAL(順$(2)(j:j)) LET 計=計+SQR((x(k)-x(k0))^2+(y(k)-y(k0))^2) LET k0=k NEXT j LET 計=計+SQR((x(1)-x(k))^2+(y(1)-y(k))^2) IF i=1 THEN LET 最短=計 LET 順min$=順$(2) ELSE CALL 保存 END IF END SUB