Как построить Гамильтонов путь в матрице?

Не тот раздел.

https://www.linux.org.ru/forum/general/ -> https://www.linux.org.ru/forum/development/

Обратись в Ссылки на некорректные сообщения (49) , чтобы перенесли.

Закрыто для недавно зареганых юзеров ((

Потому что тупняк это, закрывать разделы для анонимусов и тем более регистрантов. maxcom

напиши просьбу в теме и кастани модератора (любого? не знаю)

да эту твою просьбу пусть «подчистят» потом ;) — мой коммент наверное тоже будет не нужен

двух метапрогов ЛОР не вывезет %))

Да я уже написал в спец. тему. Ссылки на некорректные сообщения (49) (комментарий)

Он – ТС. Пусть учиться решать проблемы. Мы можем подсказывать и даже что-то делать, но если он не будет ничего делать – это ему это на пользу не пойдёт.

Раз уж мы в Development... то в Sage для этого есть hamiltonian_cycle(). Поэтому на питоне задача решается как-то так:

g = graphs.Grid2dGraph(10,10)
for i,j in [ (1,7), (2,1), (4,4), (7,2), (7,7), (9,4) ]:
    g.delete_vertex( (i,j) )
answer = g.hamiltonian_cycle(algorithm='tsp')
answer.show()

Потестить код можно на: https://sagecell.sagemath.org/

Ну типа Гамильтонов путь.

Ну, типа метод ветвей и границ ©.

желательно чтобы алгоритм работал за разумное время.

Это np-сложная задача.

Это np-сложная задача.

В случае матрицы есть специальные подходы [1] [2] [3]. И матрица у нас не большая.

Слушайте, я в алгоритмах очень плохо секу, не могли бы вы мне помочь с алгоритмом? С его реализацией, я имею ввиду.

Разберись самостоятельно. Будет больно, но зато потом будет меньше вот этого:

Слушайте, я в алгоритмах очень плохо секу

Слушайте, я в алгоритмах очень плохо секу, не могли бы вы мне помочь с алгоритмом? С его реализацией, я имею ввиду.

Ну, там парой сообщений выше и есть весь алгоритм.

Или надо без внешних средств, только стандартной библиотекой?

Если так, то в условиях «в алгоритмах очень плохо секу» про сложные специализированные алгоритмы можно забыть, лучше искать простым поиском в глубину (оно же «поиск с возвратом»).

В алгоритмах на графах есть три базовых представления графа (список рёбер, списки смежности, матрица смежности) и два базовых алгоритма (поиск в глубину, поиск в ширину). Их достаточно для простого решения большинства задач, в том числе и этой: перегоняешь свой граф в списки смежности, затем обходишь поиском в глубину, пока не найдёшь путь длинной N (где N — число вершин).

Почитать про это можно где угодно, от википедии до документации по питону (Гвидо ван Россум сочинял заметки по этому поводу). Если ты программист, то можно почитать книжку «Дискретная математика для программистов» (их вообще-то несколько с таким названием, но я уже не помню, какая лучше).

То, что ты объясняешь, мне кажется у меня такое уже есть. Алгоритм весьма прост, но уже на матрице 9х7 работает ~2.5 секунды(в зависимости от количества блоков в матрице работает чуть быстрее или чуть медленее). Мне надо чтоб в матрице 13х13 алгоритм находил бы путь ну хоть за минуты, но не дни же :))

private fun find(start: Int): Boolean {

    visited[start] = true
    path.add(start)


    if (path.size >= pathLength) {
        return true
    }


    for (j in 0 until adj[start].size) {

        if (adj[start][j] != 0 && !visited[j]) {
            if (find(j)) {
                return true
            }
        }

    }

    visited[start] = false
    path.removeAt(path.lastIndex)

    return false

}

Да, всё верно. Решение влоб на питоне даёт тот же порядок скорости:

#!/usr/bin/python
# -*- coding: utf-8 -*-
d = [[1,1,1,1,1,1,1,1],
     [1,1,1,1,1,0,1,1],
     [1,0,1,1,1,1,1,1],
     [1,1,1,1,1,1,1,1],
     [1,1,1,0,1,1,1,1],
     [1,1,1,1,1,1,1,1],
     [1,1,0,1,1,1,1,1],
     [1,1,1,1,1,1,1,1]]

def hamilton(y,x, remains):
    d[y][x] = 0 # mark as visited
    if remains == 0:
        return [(y,x)]
    found = (( x>0           and d[y][x-1]==1 and hamilton(y,x-1, remains-1) ) or
             ( x+1<len(d[y]) and d[y][x+1]==1 and hamilton(y,x+1, remains-1) ) or
             ( y>0           and d[y-1][x]==1 and hamilton(y-1,x, remains-1) ) or
             ( y+1<len(d)    and d[y+1][x]==1 and hamilton(y+1,x, remains-1) ))
    if found:
        return [(y,x)] + found
    d[y][x] = 1 # unmark

def show(path):
    chars = [ [ ".xS"[v] for v in row ] for row in d ]
    py, px = path[0]
    y, x = path[1]
    dpn = [2,0,'?',1,3][(y-py)*2+(x-px)+2] # up,left,right,down we go
    chars[py][px] = ["╴","╶","╵","╷"][dpn]
    for ny, nx in path[2:]:
        dn = [2,0,'?',1,3][(ny-y)*2+(nx-x)+2]
        chars[y][x] = ['─','?','┐','┘', '?','─','┌','└', '└','┘','│','?', '┌','┐','?','│'][dn*4+dpn]
        y, x, dpn = ny, nx, dn
    chars[y][x] = ["╶","╴","╷","╵"][dn]
    print("\n".join("".join(row) for row in chars))

if __name__ == "__main__":
    count = sum( v!=0 for row in d for v in row )
    show( hamilton(0,0, count-1) )

$ time pypy lor15331018.py
╶──────┐
┌───┐.┌┘
│.┌┐└─┘╷
└─┘└──┐│
┌─┐.┌─┘│
└┐└─┘┌─┘
┌┘.┌┐└─┐
└──┘└──┘

real	0m8,449s
user	0m8,392s
sys	0m0,052s

И никаких других простых алгоритмов мне в голову, увы, не приходит.

Из простых была динамика/поиск в ширину методом Беллмана, Хелда и Карпа. Написанная в лоб она занимает строк 20. Но она экспоненциальна по памяти и сжирает у меня всю память уже для графа 8x8.

Что-то более реалистичное к простым уже не отнесёшь. Так что если тебе не принципиально решить эту задачу, то рекомендую забить. 🙂 Но если хочется попытаться... В целом я знаю четыре направления, куда можно копать.

Во-первых, для прямоугольных grid-графов без дыр есть известные простые решения почти для любой формы (ссылки выше по треду). Если твой граф относится к ним — повезло.

Во-вторых, прямоугольные grid-графы относятся к двудольным графам со степенью <= 4. Для таких графов есть специальные алгоритмы. В частности, поиск в глубину не по вершинам, а по рёбрам.

В обычном поиске в глубину, как в исходниках выше по треду, для каждой вершины мы рекурсивно перебираем всех её соседей — найдётся ли путь где она будет следующей. В конце получаем цепочку вершин, и рёбра между ними — искомый путь.

Вот, вместо поиска вершин, можно делать поиск сразу по рёбрам — для каждого ребра рекурсивно проверять, найдётся ли гамильтонов путь, в который входит это ребро. И тут главное — аккуратно сделать этот поиск, сразу размечая рёбра в графе как точно входящие или точно не входящие в искомый путь, как только это становится известно. Например, если вершина имеет только одно ребро, то это ребро точно нужно включить в искомый путь. А если у какой-то вершины уже есть два «включенных» ребра, то остальные рёбра этой вершины можно исключить из кандидатов. И так далее.

В общих словах алгоритм довольно прост:

def алгоритм(включенные_рёбра, оставшиеся_рёбра):
    пересчитать(включенные_рёбра, оставшиеся_рёбра)
    if включенные_рёбра это ответ:
        return включенные_рёбра

    v = выбираем_вершину_из(оставшиеся_рёбра)

    for ребро in смежные_рёбра(v) from оставшиеся_рёбра:
        оставшиеся_рёбра = оставшиеся_рёбра - ребро
        result = алгоритм(включенные_рёбра+ребро, оставшиеся_рёбра)
        if result:
            return result

Исследования в направлении этого подхода начались примерно с работы D.Eppstein, и продолжаются до сих пор. Почитать про это можно, например, в работе A Fast Algorithm For Finding Hamilton Cycles. Кстати, в обоих ссылках есть не только математические выкладки, но и исходники реализации — в подобных работах это редкость.

Далее, следующее направление. Sage сводит поиск гамильтонового пути к гамильтоновому циклу (временным добавлением ещё одной вершины, связанной со всеми остальными), и затем решает как задачу коммивояжера линейного программирования (MILP — Mixed Integer Linear Programming) (исходник: generic_graph.py, искать «traveling_salesman_problem»).

Ну и для вышеупомянутого алгоритма Карпа была оптимизация, жрущая меньше памяти, но она что-то не гуглится.

Ну типа Гамильтонов путь.

Ну, типа метод ветвей и границ ©.

А как применить алгоритм по этой ссылке для поиска гамильтонового пути? Там после первой же редукции в матрице останутся только нули (если путь между вершинами есть) и бесконечности (если пути между вершинами нет). И что с ней дальше делать? Какую дугу выбирать?

Волновой алгоритм же!

Что за детский сад?

Волновой алгоритм же! Что за детский сад?

Дохнет по памяти ещё на матрице 7х7, не? Или покажи код, какой именно алгоритм ты имеешь ввиду!