A simple rout algorithm in finding the way from point (0,0) to a random point (x1,y1) in a block

5 Ansichten (letzte 30 Tage)
In the first step, I have to make the below shape! However, the program must generate black dots and red dots randomly. The number of red dots is always 10 and their coordinates are random, and of course only the correct values ​​can be between zero and 10, as well as the black dot, which is always a random dot with the same characteristic of red dots. The blue dot is always in the zero and zero coordinates. The starting point or origin is the lower left corner marked in blue. The destination point is marked in black, which in this example is in coordinates 5 and 7. Suppose that we can only move 1 unit in each step and we can only go to the destination through the green dots. The red dots are actually obstacles in the path that we must somehow get around.
The program is supposed to offer two routes:
1 shortest between origin and destination! -
2 paths that required the least number of turns.
Assumption: Consider the length of horizontal, vertical and oblique steps the same, and for the shortest path only the number of step is important.
my code so far:, but I cannot go more. since I should do it without using for and while loops. the figures I need to produce are attached to this question.
any help is really appreciated. I need a hint to do the rest.
Sincerely, Niza
clc;clear;close all;
x = 0:10;
y = 0:10;
[xx,yy]=meshgrid(x,y);
plot(xx, yy, 'bo', 'MarkerSize', 15,'markeredgecolor','b','markerfacecolor','g');
hold on;
plot(xx(1,1),yy(1,1),'o', 'MarkerSize', 15,'markeredgecolor','r','markerfacecolor','b')
annotation('textbox', [0.32, 0.06, 0.1, 0.1], 'String', "start point!")
xxr=randperm(10,10);
yyr=randperm(10,10);
xxb=randperm(10,1);
yyb=randperm(10,1);
plot(xxr, yyr, 'o', 'MarkerSize', 15,'markeredgecolor','b','markerfacecolor','r');
plot(xxb, yyb, 'o', 'MarkerSize', 15,'markeredgecolor','r','markerfacecolor','k');
axis([-1,11,-1,11])
grid on;
axis square;
hold all
xx(1,1)=NaN; yy(1,1)=NaN;
D = sqrt((xx .^ 2) + (yy .^ 2));
% Find the closest one from (0,0)
[minDistance, indexOfMin] = min(D);
closestX = xx(indexOfMin);
closestY = yy(indexOfMin);
% Mark it with red *
hold on; % Don't blow away existing points.
plot(closestX, closestY, 'r*', 'MarkerSize', 8, 'LineWidth', 2);
% Draw a line from the closest point to (0, 0)
line([0, closestX], [0, closestY], 'LineWidth', 2, 'Color', 'r');

Akzeptierte Antwort

David Hill
David Hill am 14 Jul. 2021
Bearbeitet: David Hill am 14 Jul. 2021
I would use a graph.
M=zeros(100);%adjacency matrix start
r=randperm(100,11);%ten random nodes with last node the end point
e=r(11);%end node
r=r(1:10);
for k=1:100%create adjacency matrix
if ismember(k,r)
continue;
end
idx=[k-11,k-10,k-9,k-1,k+1,k+9,k+10,k+11];
idx=idx(idx>0&idx<101&~ismember(idx,r));
if mod(k,10)==1
idx=idx(mod(idx,10)~=0);
elseif mod(k,10)==0
idx=idx(mod(idx,10)~=1);
end
M(k,idx)=1;
end
d=graph(M);%create graph
s=shortestpath(d,10,e);%find shortest path from node 10 to node e
plot(d);
  4 Kommentare
John D'Errico
John D'Errico am 14 Jul. 2021
+1. The requirement to not use a loop seems a bit silly here, but homework is what it is, I guess. Anyway, David is correct that a graph is the right way to solve it. How you build that graph is not the problem. What seems really crazy is that you could not use a loop, but that you could use graph? Sigh. :)
Farnaz Baya
Farnaz Baya am 14 Jul. 2021
Bearbeitet: Farnaz Baya am 14 Jul. 2021
@John D'Errico no not even a graph :) yeah it is a little bit hard to deal with this way but the way that I should move between points is one step at a time and then reach the black point. graph is a good Idea but the code here which @David Hill suggested me to do doesnt help me in this regard since it is not just about the shortest way it is also about the way with the least detour.

Melden Sie sich an, um zu kommentieren.

Weitere Antworten (0)

Kategorien

Mehr zu Graph and Network Algorithms finden Sie in Help Center und File Exchange

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by