|
|
Регистрация Восстановить пароль |
Повторная активизация e-mail |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
12.11.2008, 20:18 | #1 |
Пользователь
Регистрация: 17.10.2008
Сообщений: 48
|
алгоритм нахождения наилучшего маршрута между двумя заданными городами
Здравствуйте всем! У меня проблема. Очень нужно реализовать алгоритм нахождения наилучшего маршрута между двумя заданными городами, если при этом ему надо обязательно попасть в заданный пользователем города. На Delphi. Буду очень благодарна.Плиииз((((Хотя бы что-нибудь((
|
12.11.2008, 20:37 | #2 |
Высокая репутация
СуперМодератор
Регистрация: 27.07.2008
Сообщений: 15,554
|
В чем выражается наилучшесть? В кратчайшем пути или пути с наименьшим весом? Данные в виде графа или как?
E-Mail: arigato.freelance@gmail.com
|
12.11.2008, 21:17 | #3 |
Форумчанин
Регистрация: 07.10.2008
Сообщений: 213
|
Ну, конечно, лучше всего с графами сделать эту задачку. Достаточно взять книгу по дискретной математике или просто по теории графов, в разделе задач о кратчайших соединениях и путях. Например, Ерусалимского могу посоветовать. В нем неплохо описаны алгоритмы Дейкстры и Краскала. А если это задание по программированию, то можно подойти к преподавателю по дискретной математике и попросить совета у него.Вот.
|
13.11.2008, 15:35 | #4 |
Пользователь
Регистрация: 17.10.2008
Сообщений: 48
|
Нужно кратчайшие пути. Денные не в виде графа.Просто выбираются 3 города.Пользователем.И в окошко Memo выводится расчет расстояний между ними.Вот и все.Пожалуйста помогите(((((
|
13.11.2008, 16:03 | #5 | |
Высокая репутация
СуперМодератор
Регистрация: 27.07.2008
Сообщений: 15,554
|
Цитата:
(X1, Y1) - (X2, Y2) - между 1-м и 2-м городом (X1, Y1) - (X3, Y3) - между 1-м и 3-м (X2, Y2) - (X3, Y3) - между 2-м и 3-м Из этих данных можно сделать простецкий граф, вес ребра - расстояние между городами. E-Mail: arigato.freelance@gmail.com
Последний раз редактировалось Arigato; 13.11.2008 в 16:07. |
|
13.11.2008, 19:54 | #6 |
Пользователь
Регистрация: 17.10.2008
Сообщений: 48
|
Курсовик помогите((((((
Вот у меня например уже реализован алгоритм Дейкстры для другого случая. А мне нужно найти расстояние между двумя городами( которые выберет сам пользователь) и обязательно зайти в третий промежуточный город, который тоже выберет сам пользователь. Я не знаю как это сделать к сожалению. Подскажите пожалуйста(
unit Unit1; interface uses Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, Grids,Buttons; const MAXPATH = 1000; // максимальная длина пути м/д двумя вершинами MAXTOWNCOUNT = 100; // максимальное количество вершин type TForm1 = class(TForm) memRes: TMemo; sgWeights: TStringGrid; lbTowns: TListBox; editTownName: TEdit; btnAddTown: TButton; btnDeleteTown: TButton; btnClear: TButton; btnGo: TButton; btnSetTowns: TButton; btnGenerate: TButton; Label1: TLabel; Label2: TLabel; Label3: TLabel; Label4: TLabel; lblFirstTown: TLabel; lblMAXPATH: TLabel; Label5: TLabel; Label6: TLabel; ComboBox1: TComboBox; ComboBox2: TComboBox; Memo1: TMemo; Button1: TButton; procedure btnAddTownClick(Sender: TObject); procedure btnSetTownsClick(Sender: TObject); procedure sgWeightsSetEditText(Sender: TObject; ACol, ARow: Integer; const Value: String); procedure btnGenerateClick(Sender: TObject); procedure btnClearClick(Sender: TObject); procedure btnDeleteTownClick(Sender: TObject); procedure FormShow(Sender: TObject); procedure btnGoClick(Sender: TObject); procedure ComboBox1Change(Sender: TObject); procedure ComboBox2Change(Sender: TObject); private { Private declarations } // матрица весов (расстояний между городами) Weights: array [0..MAXTOWNCOUNT-1, 0..MAXTOWNCOUNT-1] of integer; // количество городов towncount: integer; // массивы для расчета // город (вершина графа) уже обсчитан Ready: array [0..MAXTOWNCOUNT-1] of boolean; // текущий кратчайший пусть до этого города из первого Paths: array [0..MAXTOWNCOUNT-1] of word; // предпоследний узел пути из первого города до этого Nodes: array [0..MAXTOWNCOUNT-1] of byte; // индекс первого города first: integer; // очистка интерфейсной таблицы весов procedure ClearGrid; // перенести данные из TStringGrid в матрицу весов procedure GetWeightsMatrix; // инициализируем расчет procedure FirstCountStep; // запускаем расчет procedure GoCount; // результаты - в мемо procedure ShowResults; // все ли вершины обсчитаны? function AllAreReady: boolean; // получить необсчитанную вершину с наименьшим путем function GetMinPath: word; public { Public declarations } end; var Form1: TForm1; implementation {$R *.dfm}uses Unit2; procedure TForm1.btnAddTownClick(Sender: TObject); //Добавить город в список begin if editTownName.Text='' then MessageDlg('Ошибка: Вы не ввели название города!', mtError, [mbOK], 0) else begin lbTowns.Items.Add(editTownName.Text ); editTownName.Text := ''; end; end; procedure TForm1.btnSetTownsClick(Sender: TObject); //Заполнить шапку таблицы названиями городов из списка var i: integer; begin sgWeights.ColCount := lbTowns.Items.Count+1; sgWeights.RowCount := lbTowns.Items.Count+1; for i:=0 to lbTowns.Items.Count-1 do begin sgWeights.Cells[i+1,0] := lbTowns.Items[i]; sgWeights.Cells[0,i+1] := lbTowns.Items[i]; end; end; procedure TForm1.sgWeightsSetEditText(Sender: TObject; ACol, ARow: Integer; const Value: String); //При изменении ячейки таблицы, вставляем то же значение в симметричную ячейку begin // делаем матрицу симметричной принудительно sgWeights.Cells[ARow,ACol] := Value; end; procedure TForm1.btnGenerateClick(Sender: TObject); //Сгенерировать расстояния между городамислучайным образом var i, j: integer; flag: real; // существует ли путь begin ClearGrid; for i:=1 to sgWeights.ColCount-1 do begin sgWeights.Cells[i,i] := '0'; for j:=i+1 to sgWeights.RowCount-1 do begin flag := random; if (flag>0.5) then begin sgWeights.Cells[i,j] := IntToStr(random(MAXPATH)); sgWeights.Cells[j,i] := sgWeights.Cells[i,j]; end; end; end; end; procedure TForm1.ClearGrid; //Очистить интерфейсную таблицу расстояний между городами var i, j: integer; begin for i:=1 to sgWeights.RowCount-1 do for j:=1 to sgWeights.ColCount-1 do sgWeights.Cells[i,j] := ''; end; procedure TForm1.btnClearClick(Sender: TObject); //Очистить список городов begin lbTowns.Items.Clear; end; |
13.11.2008, 19:59 | #7 |
Пользователь
Регистрация: 17.10.2008
Сообщений: 48
|
Курсовик помогите((((((
Этой мой код ..алгоритм Дейкстры. Это первая часть работы моего курсовика. Есть ещё вторая. А то что прошу это третья
|
13.11.2008, 20:15 | #8 |
Высокая репутация
СуперМодератор
Регистрация: 27.07.2008
Сообщений: 15,554
|
Всего 3 города, пользователю нужно попасть из города N в город M через 3-й? Странная задача, тут ни каких даже графов не надо, просто просуммировать расстояния между этими городами и все.
E-Mail: arigato.freelance@gmail.com
|
13.11.2008, 20:20 | #9 |
Старожил
Регистрация: 20.04.2008
Сообщений: 5,526
|
min(A-C-B)=min(A-C)+min(C-B) ???????????
программа — запись алгоритма на языке понятном транслятору
|
13.11.2008, 21:21 | #10 |
Высокая репутация
СуперМодератор
Регистрация: 27.07.2008
Сообщений: 15,554
|
А как тут вообще может быть минимальное расстояние? У нас 3 города, хотим попасть из 1-го в 3-й, через 2-й. Считаем длину отрезка, соединяющего 1-й и 2-й город и прибавляем длину отрезка между 2-м и 3-м городом. Или я чего-то не понял в задаче?
E-Mail: arigato.freelance@gmail.com
|
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Копирование файлов и каталогов перетаскиваением между двумя окнами | SANTA_KLAUD | Общие вопросы Delphi | 3 | 28.05.2008 21:52 |
алгоритм нахождения интеграла методом трапеций | pirozho4ek | Паскаль, Turbo Pascal, PascalABC.NET | 2 | 11.06.2007 02:44 |
Надо в RichEdit Удалить все строки между двумя пустыми | Stas))) | Компоненты Delphi | 7 | 28.05.2007 16:49 |
Как из Delphi программно создать связь между двумя базами Access? | Dimm | Microsoft Office Access | 6 | 12.01.2007 14:35 |