Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > IT форум > Помощь студентам
Регистрация

Восстановить пароль

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 18.11.2012, 14:12   #1
kokadyyyyyyy
Пользователь
 
Аватар для kokadyyyyyyy
 
Регистрация: 23.10.2011
Сообщений: 13
По умолчанию коммивояжер перебором (delphi)

Здравствуйте,буду очень признательна,если поможете решить задачу,ну то есть закодировать)
Суть задачи:Имеется n городов, расстояния между которыми заданы. Коммивояжеру необходимо выйти из какого-то города, побывать во всех остальных городах точно по одному разу, и вернуться в исходный город. Маршрут должен быть минимальным по длине, т.к. кол-во городов 5-10 ,то перебором удобней.
Код имеется, но есть ошибки
Код:
unit MainUnit;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, Buttons, StdCtrls, Mask, Grids, ComCtrls, Menus;

type
  TForm1 = class(TForm)
    ud1: TUpDown;
    strngrd1: TStringGrid;
    edt1: TEdit;
    mm1: TMainMenu;
    N1: TMenuItem;
    N2: TMenuItem;
    N3: TMenuItem;
    N6: TMenuItem;
    N7: TMenuItem;
    N8: TMenuItem;
    N9: TMenuItem;
    btn1: TButton;
    btn2: TButton;
    edt2: TEdit;
    ud2: TUpDown;
    lst1: TListBox;
    procedure solve;
    procedure sortlines (v, count: byte; cost: integer);
    procedure N6Click(Sender: TObject);
    procedure aboutClick(Sender: TObject);
    procedure FormShow(Sender: TObject);
    procedure edt2Change(Sender: TObject);
    procedure edt1Change(Sender: TObject);
    procedure btn1Click(Sender: TObject);
    procedure btn2Click(Sender: TObject);
  private
    { Private declarations }
  public
    { Public declarations }

   end;   const maxv=10;
var
  Form1: TForm1;
	
	a: array[1 .. maxv,1 .. maxv] of integer;
	b: array[1 .. maxv, 1 .. maxv] of byte;
	way, best: array[1 .. maxv] of byte;
  
	nnew: array[1 .. maxv] of boolean;
	bestcost: integer;
	n, i: integer;


implementation

uses
  aboutUnit;

{$R *.dfm}

procedure TForm1.sortlines;
var
	k, i, j: integer;
	w: integer;
begin
	for i:=1 to n do
		for j:=1 to n do b[i,j]:=j;
	for k:=1 to n do
		for i:=1 to n-1 do
			for j:=i+1 to n do
				if a[k,b[k,i]]>a[k,b[k,j]] then begin
					w:=b[k,i]; b[k,i]:=b[k,j]; b[k,j]:=w;
				end;
end;

procedure TForm1.solve ;//(v, count: byte; cost: integer); 
var i: integer;
v, count: byte; cost: integer;
begin
	if cost > bestcost then exit;
	if count=n then begin
		cost:=cost+a[v,1];
		way[n]:=v;
		if cost<bestcost then begin
			bestcost:=cost;
			best:=way;
		end;
		exit;
	end;
	nnew[v]:=false;
	way[count]:=v;
	for i:=1 to n do
		if nnew[b[v,i]] then solve([b[v,i]],count+1,cost+a[v,[b[v,i]]);
	nnew[v]:=true;
end;

begin
	{//init;
	sortlines;
	solve(1,1,0);
	writeln(bestcost:4
	for i:=1 to n do write(best[i],' '); writeln;  }
end.


procedure TForm1.N6Click(Sender: TObject);
begin
  Close;
end;

procedure TForm1.aboutClick(Sender: TObject);
begin
Form2.ShowModal;
end;

procedure TForm1.FormShow(Sender: TObject);
begin
strngrd1.Cells[0,0]:='№';
end;

procedure TForm1.edt2Change(Sender: TObject);
var
  J,N,M:Integer;
begin
  M:=StrToInt(edt1.Text);
  N:=StrToInt(edt2.Text);
  strngrd1.RowCount:=N+1;
  strngrd1.Cells[0,N]:=edt2.Text;
  for J:=1 to M do
    begin
      If strngrd1.Cells[J,N]=''
        then strngrd1.Cells[J,N]:='0';
end;
end;
procedure TForm1.edt1Change(Sender: TObject);
var
  I,N,M:Integer;
begin
  M:= StrToInt(edt1.Text);
  N:=StrToInt(edt2.Text);
  strngrd1.ColCount:=M+1;
  strngrd1.Cells[M,0]:=edt1.Text;
  for I:=1 to N do
    begin
      If strngrd1.Cells[M,I]=''
        then strngrd1.Cells[M,I]:='0';
end;
end;
procedure TForm1.btn1Click(Sender: TObject);
begin

             sortlines;
	solve(1,1,0);
	//writeln(bestcost:4);
	for i:=1 to n do //write(best[i],' '); writeln;
                                      lst1.Items.Add('->'+IntToStr(best[i]);
end;
   end;


procedure TForm1.btn2Click(Sender: TObject);
begin
// strngrd1.Cols [i].Clear;
 //strngrd1.Rows[j].Clear;
 //strngrd1.RowCount:=2;
 //strngrd1.Rows[1]:='';
end;


end.
не пугайтесь размера кода,это все из-за меню)
kokadyyyyyyy вне форума Ответить с цитированием
Старый 19.11.2012, 18:19   #2
kokadyyyyyyy
Пользователь
 
Аватар для kokadyyyyyyy
 
Регистрация: 23.10.2011
Сообщений: 13
По умолчанию

ни кто не знает ? печаль (
kokadyyyyyyy вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Delphi. Жадный алгоритм. Коммивояжер ZidanCo Общие вопросы Delphi 1 07.03.2012 10:29
Коммивояжер в делфи( LeToR Помощь студентам 0 24.12.2011 08:33
Коммивояжер VaSS Помощь студентам 0 04.05.2010 21:44
Помогите с перебором вариантов. Fidel157 Общие вопросы C/C++ 3 07.07.2009 10:26
Объяснение к задаче коммивояжер. enik pi Помощь студентам 2 14.06.2007 00:54