Поиск пути

← →
Sam Stone © (2006-04-01 10:27) [0]

Имеется "карта"(матрица M*N) с препятствиями, требуется найти путь от точки А до Б, учитывая то, что путь должен быть шириной не меньше К клеток на всем пути. Подскажите, пожалуйста, как можно решить сабж.

← →
TUser © (2006-04-01 19:02) [1]

Что такое ширина пути? И какой из путей надо искать - кратчайший или любой?

← →
Sam Stone © (2006-04-01 19:58) [2]

Путь любой. Ширина пути это его ширина в клетках. Чтобы не крутиться с абстракцией опишу по предметной области :) : рисуется склад, вид сверху, карта представляет собой помещение склада, объекты на ней - секции с полками. Чтобы подъехать к секции погрузчику необходимо определенное место, которое так же отражается на карте как зона погрузки. Грубо говоря надо проверить путь до каждой секции(его наличие, чтоб не было запертых участков) и ширину этого проезда. Перейти к ширине проезда не представляется возможным, потому что секции могут быть произвольной глубины - под разные грузы. Т.е происходит масштабирование реальных метров в клетки на рисуемой "карте".

← →
Kolan © (2006-04-01 21:21) [3]

Могу дать похожий проект(Учебный).

Уже не помню тут реализован метод равных цен. Пример такой:
procedure TEqualPricesManager.BuidWay(var Error: Boolean); var TempCell: TCellAndWayPrice; TempNode: TEqualPricesTreeNode; // I: Integer; begin // TODO: Ñäåëàòü íåñêîëüêî òèïîâ îøèáîê. Error := False; if (not ((FFieled.StartCell = nil) or (FFieled.EndCell = nil))) and (FFieled.StartCell <> FFieled.EndCell) then begin TempNode := TEqualPricesTreeNode.Create; TempNode.Data := TCellAndWayPrice.Create; TempNode.Data.Cell := TCustomCell.Create; TempNode.Data.Cell.SetCell(FFieled.StartCell.CellType, FFieled.StartCell.Data, FFieled.StartCell.Coordinates); FOpenedList.Add(TempNode.Data, nil); (FOpenedList.Head as TEqualPricesTreeNode).Data.WayPrice := 0; TempNode.Free; TempNode := nil; I := 0; while FOpenedList <> nil do begin I := I + 1; if FOpenedList.Head = nil then begin Error := True; Exit; end; // { PostMessage(FFormHandle, SX_M, 0, 0); Application.ProcessMessages; } // TempCell := FOpenedList.Extract; // { PostMessage(FFormHandle, SX_M, 0, 0); Application.ProcessMessages; } // if TempCell.Cell.CellType = ctSelectedEnd then begin FAnswerTree.IsNodePresent(TempCell, FAnswerTree.TreeRootList, TempNode); BuildLines(TempNode); TempCell.Free; PostMessage(FFormHandle, SX_M, 0, 0); Exit; end; if FAnswerTree.TreeRoot = nil then FAnswerTree.Add(nil, TempCell); FAnswerTree.IsNodePresent(TempCell, FAnswerTree.TreeRootList, TempNode); TempCell.Free; OpenCell(TempNode.Data, TempNode); // { PostMessage(FFormHandle, SX_M, 0, 0); Application.ProcessMessages; } // end; end; PostMessage(FFormHandle, SX_M, 0, 0); end;

Здесь рекурсивно клетки окрываются на подобии сапера...

← →
Sam Stone © (2006-04-01 21:32) [4]

> Kolan © (01.04.06 21:21) [3]
Поиск пути можно на DelphiGFX взять. Например, алгоритм А*. Тут нюанс - как при поиске учесть ширину прохода.

← →
Kolan © (2006-04-01 22:30) [5]

Незнаю тогда. Пример чесно сказать не понял....

← →
так себе (2006-04-02 18:49) [6]

Ищи книгу Никиты Культина "Основы программирования в Delphi 7". Там приводится пример поиска маршрута с использованием мех-ма рекурсии. Если найду дискету к книге - брошу пример.
В книге Рода Стивенса "Delphi гоовые алгоритмы" в главе "Сетевые алгоритмы" также рассмотрен пример и методика определения кратчайшего пути.
Пример из первой книги:
object Form1: TForm1 Left = 216 Top = 143 Width = 383 Height = 319 Caption = "Ïîèñê ìèíèìàëüíîãî ìàðøðóòà" Color = clBtnFace Font.Charset = DEFAULT_CHARSET Font.Color = clWindowText Font.Height = -11 Font.Name = "MS Sans Serif" Font.Style = [] OldCreateOrder = True OnActivate = FormActivate PixelsPerInch = 96 TextHeight = 13 object Label1: TLabel Left = 235 Top = 88 Width = 125 Height = 113 AutoSize = False WordWrap = True end object Label2: TLabel Left = 24 Top = 224 Width = 86 Height = 13 Caption = "Íà÷àëüíàÿ òî÷êà" end object Label3: TLabel Left = 24 Top = 256 Width = 79 Height = 13 Caption = "Êîíå÷íàÿ òî÷êà" end object Label4: TLabel Left = 24 Top = 8 Width = 87 Height = 13 Caption = "Îïèñàíèå êàðòû " end object StringGrid1: TStringGrid Left = 24 Top = 32 Width = 191 Height = 169 ColCount = 11 DefaultColWidth = 16 DefaultRowHeight = 14 RowCount = 11 Options = [goFixedVertLine, goFixedHorzLine, goVertLine, goHorzLine, goRangeSelect, goEditing] ScrollBars = ssNone TabOrder = 0 end object Edit1: TEdit Left = 120 Top = 216 Width = 33 Height = 21 TabOrder = 1 Text = "1" end object Edit2: TEdit Left = 120 Top = 248 Width = 33 Height = 21 TabOrder = 2 Text = "5" end object Button1: TButton Left = 232 Top = 32 Width = 75 Height = 25 Caption = "Ïîèñê" TabOrder = 3 OnClick = Button1Click end end

unit road2_; interface uses Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Grids; type TForm1 = class(TForm) StringGrid1: TStringGrid; Edit1: TEdit; Edit2: TEdit; Label1: TLabel; Label2: TLabel; Label3: TLabel; Button1: TButton; Label4: TLabel; procedure FormActivate(Sender: TObject); procedure Button1Click(Sender: TObject); private { Private declarations } public { Public declarations } end; var Form1: TForm1; implementation {$R *.DFM} procedure TForm1.FormActivate(Sender: TObject); var i:integer; begin // нумерация строк for i:=1 to 10 do StringGrid1.Cells[0,i]:=IntToStr(i); // нумерация колонок for i:=1 to 10 do StringGrid1.Cells[i,0]:=IntToStr(i); // описание предопределенной карты StringGrid1.Cells[1,2]:="1"; StringGrid1.Cells[2,1]:="1"; StringGrid1.Cells[1,3]:="1"; StringGrid1.Cells[3,1]:="1"; StringGrid1.Cells[1,4]:="1"; StringGrid1.Cells[4,1]:="1"; StringGrid1.Cells[3,7]:="1"; StringGrid1.Cells[7,3]:="1"; StringGrid1.Cells[4,6]:="1"; StringGrid1.Cells[6,4]:="1"; StringGrid1.Cells[5,6]:="1"; StringGrid1.Cells[6,5]:="1"; StringGrid1.Cells[5,7]:="1"; StringGrid1.Cells[7,5]:="1"; StringGrid1.Cells[6,7]:="1"; StringGrid1.Cells[7,6]:="1"; end; procedure TForm1.Button1Click(Sender: TObject); const N=10;{ кол-во вершин графа} var map:array[1..N,1..N]of integer;{ Карта. map[i,j]не 0,если точки i и j соединены } road:array[1..N]of integer; { Дорога - номера точек карты } incl:array[1..N]of boolean; { incl[i]равен TRUE, если точка с номером i включена в road } start,finish:integer; { Начальная и конечная точки } found:boolean; len:integer; { длинна найденного (минимального) маршрута } c_len:integer; { длина текущего (формируемого) маршрута } i,j:integer; procedure step(s,f,p:integer); var c:integer;{ Номер точки, в которую делаем очередной шаг } i:integer; begin if s=f then begin len:=c_len;{ сохраним длину найденного маршрута } { вывод найденного маршрута } for i:=1 to p-1 do Label1.caption:=Label1.caption+" "+IntToStr(road[i]); Label1.caption:=Label1.caption +", длина:"+IntToStr(len)+#13; end else { выберем очередную точку } for c:=1 to N do { проверяем все вершины } if(map[s,c]<> 0)and(NOT incl[c]) and((len=0)or(c_len+map[s,c]< len)) then begin { точка соединена с текущей, но не включена в маршрут} road[p]:=c;{ добавим вершину в путь } incl[c]:=TRUE;{ пометим вершину как включенную } c_len:=c_len+map[s,c]; step(c,f,p+1); incl[c]:=FALSE; road[p]:=0; c_len:=c_len-map[s,c]; end; end;{ конец процедуры step } begin Label1.caption:=""; { инициализация массивов } for i:=1 to N do road[i]:=0; for i:=1 to N do incl[i]:=FALSE; { ввод описания карты из SrtingGrid.Cells} for i:=1 to N do for j:=1 to N do if StringGrid1.Cells[i,j] <> "" then map[i,j]:=StrToInt(StringGrid1.Cells[i,j]) else map[i,j]:=0; len:=0; // длина найденного (минимального) маршрута c_len:=0; // длина текущего (формируемого) маршрута start:=StrToInt(Edit1.text); finish:=StrToInt(Edit2.text); road[1]:=start;{ внесем точку в маршрут } incl[start]:=TRUE;{ пометим ее как включенную } step(start,finish,2);{ищем вторую точку маршрута } // проверим, найден ли хотя бы один путь if not found then Label1.caption:="Указанные точки не соединены!"; end; end.

← →
Sam Stone © (2006-04-02 20:17) [7]

Во-первых, что вводится в эдитах? Во-вторых, переменной found нигде не приваивается значение ) В-третьих, меня, похоже, так и не поняли )

Вот рисунок: http://www.ljplus.ru/img/s/a/samstone/base.GIF
Синие прямоугольники - секции для грузов (см (01.04.06 19:58) [2]). Серая зона - незанятое пространство, зеленая - необходимое для подъезда погрузчика место. Для каждой секции обвел пунктиром(при наложении зон отметил разным цветом). Красный кватрат - вход №1, желтый квадрат - вход №2. Цель - черный квадрат. Алгоритмом поиска можно добраться до "выхода" из обеих начальных точек. При моем ограничении на ширину проезда - только из точки №1(красный квадрат). Желтый "вход" оказывается запертым(расстояние м/д секциями слишком мало для прохода). Если рассматривать желтый квадрат как вторую конечную точку, то до нее нельзя доехать по аналогичной причине.

← →
так себе (2006-04-02 20:58) [8]

В эдитах как раз и вводится начальная и конечная точка

← →
Sam Stone © (2006-04-02 21:50) [9]

Через 2 эдита задаются 2 двумерные координаты? Еще раз повторю: переменной Found значение нигде не присваивается, так что пользы от кода нет. Реализовать поиск по карте я и сам могу, мне как-то надо учесть ширину пути

← →
Kolan © (2006-04-02 21:59) [10]

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

> Kolan © (02.04.06 21:59) [10]
Путь идет по самому дешевому пути, поэтому высокие цены просто обойдутся алгоритмом.
ты писал: Здесь рекурсивно клетки окрываются на подобии сапера...
Это что-то типа этого: http://delphigfx.mastak.ru/doc/path/path_fim.png ?

По сути тот же волновой подойдет. Ограничение ведь по переходу в соседнюю или запрет по оному - можно же формализовать.
Допустим ширина 2 нужна. А - это вертикальный прямоугольник 2 на 1. " в вертикаль, и один в горизонталь. 0 - стенка. И имеем.
0 0 0 А А А А А А 0
Переход из нижнего ряда в верхний не возможен, ибо при движении по вертикали ограничение в 1. Соответственно будет восприниматься как стенка горизонтальная. Поэтому тот же волновой, но с чуть усложненной функцией определения стенок.

Я надумал таскать прямоугольник поклеточно, через левую или правую руку, ибо все равно не оптимальный путь нужен, а проверка. Хотя мож стоит и поэкспериментировать волновым, придумав енту самую функцию определения стенок )

> Sam Stone © (03.04.06 09:27) [13]

Дык. Тебе про это и пишу. Суть ведь всего подобного в одном - стенки. То есть - возможен переход или нет. А разница в том. что одни стенки у тебя в итоге меняются. То есть имея одноклеточную стеночную реализацию, ты переходишь к другой стеночной реализации и в ней все тоже. Возможна пара ньюансов, но это я думаю, мелочи.

Поиск пути Найти похожие ветки