Как обойти все вершины графа кратчайшим путем?

Question

[ukoHka]

Даны n точек на плоскости двумя неотрицательными координатами. Игроку нужно обойти их все. Какое минимальное расстояние нужно пройти, чтобы обойти все точки, если игрок всегда начинает с точки (0,0)?
Я знаю, что это задача на графы, знаю, что есть куча алгоритмов, алгоритм Дейкстры может помочь решить, возможно это гамильтонов граф и т.д. Но разобраться во всем этом не смог, поэтому интересует именно реализация.
Пока что имеется только: считал точки в массив, построил матрицу смежности, которая является симметричной, относительно главной диагонали, а дальше никак. В матрице смежности в a[i,j] записано расстояние между i-й и j-й точкой, включая и стартовую точку.

Answer 1

[longclaps]

Это - задача коммивояжера, решается перебором.
Вот тебе решение на питоне, на паскале ты уж как-нибудь сам )

from math import hypot

# тестовые варианты наборов точек
points = [(3, 4), (7, 7)]
points = [(3, 0), (3, 4), (6, 4)]
points = [(1, 0), (1, 8), (0, 8)]

INF = 1e20  # будем считать, что это - бесконечность
def f(startx, starty):
    res = INF
    for i, (x, y) in enumerate(points):
        if x >= 0:
            points[i] = (-1, -1)  # подменяю использованую точку на фиктивную
            t = hypot(startx - x, starty - y) + f(x, y)  # вот рекурсия, как обещал
            if res > t:
                res = t
            points[i] = (x, y)  # восстанавливаю точку
    if res == INF:  # не нашлось ни одной неиспользованой точки
        res = 0
    return res

print(f(0, 0))  # стартую из начала координат

Comments

[ukoHka]

В том-то и проблема, что я никак не соображу, как его перебрать.

[longclaps]

ukoHka: напиши рекурсивную функцию с аргументом - набором непосещеных точек и результатом - минимальным расстоянием пути их обхода.

[ukoHka]

longclaps: именно это я и пытался сделать, до того, как написал сюда. Написать рекурсивную функцию.

[ukoHka]

Мда, я создал матрицу смежности и привязался к ней, а оказывается нужно оригинальный массив брать.

function dist(x1, y1, x2, y2: integer) :real;
	begin
		dist := sqrt(sqr(x2-x1) + sqr(y2-y1));
	end;
	
	function solve(startx, starty: integer):real;
	var d,m: real;
		i,x,y:integer;
	begin
		m := max;		
		for i:= 0 to n do 
		begin			
			x := a[i,1];
			y := a[i,2];
			if a[i,1] >= 0 then
			begin
				a[i,1] := -1;
				a[i,2] := -1;
				d := dist(startx,starty,x,y) + solve(x,y);
				if m > d then m := d;
				a[i,1] := x;
				a[i,2] := y;
			end;			
		end;
		if m = max then m := 0;
		solve := m;
	end;

[ukoHka]

longclaps: А какова сложность этого алгоритма? Что-то у меня оно долго выполняется при n в районе 10.

[longclaps]

ukoHka: n!
Вместо вызова dist посчитай 1 раз "матрицу смежности"[i,j], а для точек просто держи массив boolean - выиграешь сколько-то, но всё равно загнёштся, не на 10, так на 11.