Комбинаторика и графы

@lexus_ilia · Регистрация: 24.09.2008

Студворк — интернет-сервис помощи студентам

Есть задание:
На плоскости заданы n точек своими координатами. Построить ломаную, имеющую наименьшее число отрезков, проходящую через эти точки, причем через каждую точку ломаная должна проходить лишь один раз.

И есть вопрос от меня...Причём тут графы? Может я не очень уловил их суть, но разве эта кривая не будет строиться по принципу:"Берём самую отдалённую нижнюю точку и соединяем с ближайшей и т.д. пока не закончатся точки".
Или если взять комбинаторику, так она тут тож вроде никаким боком...
Короче прошу, если вам не сложно, разъяснений, каким боком прикинуть сюда графы(узлами будут точки, а рёбра прямые соединяющие их, а потом найти кратчайщий путь от 1-ого узла до последнего?Так если так взять, то у каждого узла будет n-1 ребро, а не многоват-ли?А потом использовать Алгоритм Дейкстры для поиска пути?) у меня есть только такое объяснение...

@Puporev · 22.11.2008, 09:57

Скорее всего что-то упущено или исковеркано в условии. В таком виде действительно провести n-1 отрезок от самой левой до самой правой точки и все.

@pascal65536 · 22.11.2008, 12:28

ИМХО ломаная должна иметь при этом минимальный путь.

@Puporev · 22.11.2008, 12:36

ИМХО ломаная должна иметь при этом минимальный путь.

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

@lexus_ilia · 22.11.2008, 19:18 **[ТС]**

короче я алгоритм походу понял, берём нумеруем наши точки от 1 до n потом соединяем каждую точку с другой, а ребру получившейся между ними придаём вес, равный расстоянию между 2-мя точками, а потом когда все рёбра готовы, ищем с какой точки начинаем и какой заканчиваем, а потом ищем путь между ними с минимальным весом...

@pascal65536 · 22.11.2008, 19:29

Нумеруем все точки (пусть их будет 8), потом начинается переборная задача.
Перебираем все последовательности
от 12345678, 12345687, 12345768 и т.д. до 87654321 итого 8! способов.
для каждой последовательности ищем длину ломаной
самая короткая - и есть искомый результат

в гугле ищем задачу коммивояжера, это почти тоже самое.

@lexus_ilia · 22.11.2008, 19:30 **[ТС]**

не-не-не проще использовать Алгоритм Дейкстры, он проще и лу4ше...

@pascal65536 · 22.11.2008, 19:49

Сообщение от lexus_ilia

не-не-не проще использовать Алгоритм Дейкстры, он проще и лу4ше...

Алгоритм Дейкстры оправдал бы себя, если граф был бы неполным, а судя из постановки задачи, вершинами графа являются точки на плоскости, а ребрами - отрезки, которыми можно эти точки соединить. При таком раскладе сложность алгоритма Дейкстры равна (N-1)! тоже самое, о чем я говорил.

@lexus_ilia · 22.11.2008, 20:05 **[ТС]**

Ты плохо посмотрел инфу по его алгоритму, т.к. "Алгоритм Дейкстры имеет сложность N^2" а это намного меньше чем N! можешь Тут глянуть.

@pascal65536 · 22.11.2008, 20:07

Сообщение от lexus_ilia

Ты плохо посмотрел инфу по его алгоритму, т.к. "Алгоритм Дейкстры имеет сложность N^2" а это намного меньше чем N! можешь Тут глянуть.

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

Оттуда же

@lexus_ilia · 27.11.2008, 03:16 **[ТС]**

Есть вопрос, решил я эту задачу использовал свой алгоритм ( а может и не свой, я уже не очень уверен в чём-то) вот листинг программы:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
Program laba15a;
Type
 mas=array[1..2] of integer;
 matr=array[1..2] of ^mas;
var
 g:^matr;
 x,y:^mas;
 l:longint;
 i,n,min,mini,man,s,j,k:integer;
begin
 Writeln('BBedute KoLu4ecTBo To4eK');
 readln(n);
 l:=MemAvail;
 Getmem(x,Sizeof(mas));
 Getmem(y,sizeof(mas));
 Writeln('BBedute koopduHaTbl To4eK');
 For i:=1 to n do
 begin
  Write('X[' ,i, ']=');
  readln(x^[i]);
  Write('Y[' ,i, ']=');
  readln(y^[i]);
 end;
 Getmem(g,SizeOF(mas)*n);
 for i:=1 to n do
 begin
  getmem(g^[i],2*n);
  for j:=1 to n do
   if j<>i then
    g^[i]^[j]:=round(sqrt(sqr(x^[j]-x^[i])+sqr(y^[j]-y^[i])))
   else
    g^[i]^[j]:=32000;
 end;
 Writeln('haLLia matPuL/a...');
  for i:=1 to n do
  begin
   for j:=1 to n do
    write(g^[i]^[j], ' ');
   writeln;
  end;
  readln;
  min:=x^[1];
  mini:=1;
  for i:=2 to n do
   if x^[i]<min then
   begin
    min:=x^[i];
    mini:=i;
   end;
  Write(mini);
  FreeMem(x,Sizeof(mas));
  FreeMem(y,Sizeof(mas));
 
  for k:=1 to n-1 do
  begin
   man:=mini;
   min:=g^[man]^[1];
   mini:=1;
   for j:=2 to n do
    if g^[man]^[j]<min then
    begin
     min:=g^[man]^[j];
     mini:=j;
    end;
   Write(' -> ' ,mini);
   s:=s+g^[man]^[mini];
   for i:=1 to n do
    g^[i]^[man]:=32000;
  end;
  for i:=1 to n do
   freemem(g^[i],2*n);
  freemem(g,SizeOF(mas)*n);
 
  Writeln;
  {Writeln('s=' ,s);
  writeln('naM9tu do  ' ,l);
  Writeln('naM9tu noCle  ' ,MemAvail);
  Writeln('He ocBobojDeHHou  ' ,l-memAvail);}
  readln;
end.

Есть проблема при вводе 6 и > n выдаёт 207 ошибку, подскажите из-за чего, пошагово проверял, т.е. получается при присваивании g[6,i]

Code
1
g^[i]^[j]:=round(sqrt(sqr(x^[j]-x^[i])+sqr(y^[j]-y^[i])))

происходит ошибка, не могу понять почему.Наведите на мысль пжлст.

Добавлено через 2 минуты 29 секунд
мот из-за типа integer?

Добавлено через 25 минут 30 секунд
Да и ошибку выдаёт если ввожу вот такие значения:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
n=6
x[1]=2
y[1]=3
x[2]=3
y[2]=-2
x[3]=-2
y[3]=-1
x[4]=-4
y[4]=2
x[5]=-5
y[5]=-2
x[6]=-6
y[6]=3

Добавлено через 2 часа 0 минут 20 секунд
Всё помощь не нужна, сделал сам, проблема была в некоторых строчках, а именно (если кому-то надо):

Code
1
2
Getmem(x,Sizeof(mas));
 Getmem(y,sizeof(mas));

и вот в этой:

Code
1
getmem(g^[i],2*n)

Заменил их на

Code
1
2
Getmem(x,Sizeof(mas)*n);
 Getmem(y,sizeof(mas)*n);

и на...

Code
1
getmem(g^[i],sizeof(mas)*n)

Новые блоги и статьи Все статьи Все блоги /
Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:
Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .	Модульная разработка через nuget packages DevAlt 07.03.2026 Сложившийся в . Net-среде способ разработки чаще всего предполагает монорепозиторий в котором находятся все исходники. При создании нового решения, мы просто добавляем нужные проекты и имеем. . .	Модульный подход на примере F# DevAlt 06.03.2026 В блоге дяди Боба наткнулся на такое определение: В этой книге («Подход, основанный на вариантах использования») Ивар утверждает, что архитектура программного обеспечения — это структуры,. . .

@lexus_ilia 3067 / 727 / 69 Регистрация: 24.09.2008 Сообщений: 1,531

	Комбинаторика и графы 22.11.2008, 03:13. Показов 2413. Ответов 10 Метки нет (Все метки) Есть задание: На плоскости заданы n точек своими координатами. Построить ломаную, имеющую наименьшее число отрезков, проходящую через эти точки, причем через каждую точку ломаная должна проходить лишь один раз. И есть вопрос от меня...Причём тут графы? Может я не очень уловил их суть, но разве эта кривая не будет строиться по принципу:"Берём самую отдалённую нижнюю точку и соединяем с ближайшей и т.д. пока не закончатся точки". Или если взять комбинаторику, так она тут тож вроде никаким боком... Короче прошу, если вам не сложно, разъяснений, каким боком прикинуть сюда графы(узлами будут точки, а рёбра прямые соединяющие их, а потом найти кратчайщий путь от 1-ого узла до последнего?Так если так взять, то у каждого узла будет n-1 ребро, а не многоват-ли?А потом использовать Алгоритм Дейкстры для поиска пути?) у меня есть только такое объяснение... 0

@Puporev Почетный модератор 64315 / 47611 / 32743 Регистрация: 18.05.2008 Сообщений: 115,167
	22.11.2008, 09:57
	Скорее всего что-то упущено или исковеркано в условии. В таком виде действительно провести n-1 отрезок от самой левой до самой правой точки и все. 0

@pascal65536 11 / 11 / 3 Регистрация: 26.09.2008 Сообщений: 77
	22.11.2008, 12:28
	ИМХО ломаная должна иметь при этом минимальный путь. 0

@lexus_ilia 3067 / 727 / 69 Регистрация: 24.09.2008 Сообщений: 1,531
	22.11.2008, 19:18 [ТС]
	короче я алгоритм походу понял, берём нумеруем наши точки от 1 до n потом соединяем каждую точку с другой, а ребру получившейся между ними придаём вес, равный расстоянию между 2-мя точками, а потом когда все рёбра готовы, ищем с какой точки начинаем и какой заканчиваем, а потом ищем путь между ними с минимальным весом... 0

@pascal65536 11 / 11 / 3 Регистрация: 26.09.2008 Сообщений: 77
	22.11.2008, 19:29
	Нумеруем все точки (пусть их будет 8), потом начинается переборная задача. Перебираем все последовательности от 12345678, 12345687, 12345768 и т.д. до 87654321 итого 8! способов. для каждой последовательности ищем длину ломаной самая короткая - и есть искомый результат в гугле ищем задачу коммивояжера, это почти тоже самое. 0

@lexus_ilia 3067 / 727 / 69 Регистрация: 24.09.2008 Сообщений: 1,531
	22.11.2008, 19:30 [ТС]
	не-не-не проще использовать Алгоритм Дейкстры, он проще и лу4ше... 0

@lexus_ilia 3067 / 727 / 69 Регистрация: 24.09.2008 Сообщений: 1,531
	22.11.2008, 20:05 [ТС]
	Ты плохо посмотрел инфу по его алгоритму, т.к. "Алгоритм Дейкстры имеет сложность N^2" а это намного меньше чем N! можешь Тут глянуть. 0