This is a simple case of the state matrix of the final state. Sorry that the pseudo-code was in C # style, but it was easier to express the idea with objects.
First, we construct the matrix of highways. Read my description of what a trunk matrix is (don't worry about the FSM answer, just an explanation of the trunk matrix). What are the testing strategies for large state machines? .
However, the limitations you describe make it a random, simple state machine. This is the simplest state machine with full coverage.
For a simple case from 5 airports,
vert nodes = src / entry points,
nodes horiz = dst / exit points.
A1 A2 A3 A4 A5 A1 x A2 x A3 x A4 x A5 x
Note that for each row, as well as for each column, there should be no more than one transition.
To get the path to the car, you sort the matrix into
A1 A2 A3 A4 A5 A2 x A1 x A3 x A4 x A5 x
Or sort by the diagonal square matrix - an eigenvector of ordered pairs.
A1 A2 A3 A4 A5 A2 x A5 x A1 x A3 x A4 x
where ordered pairs are a list of tickets:
a2: a1, a5: a2, a1: a3, a3: a4, a4: a5.
or in a more formal notation,
<a2,a1>, <a5,a2>, <a1,a3>, <a3,a4>, <a4,a5>.
Hmmm .. ordered couples huh? A hint of recursion in Lisp?
<a2,<a1,<a3,<a4,a5>>>>
There are two modes of operation of the machine:
- travel planning - you don’t know how many airports there are, and you need a general travel plan for an indefinite number of airports
- restoring a trip - you have all the tickets for the dead end of your last trip but they are all one big stack in your glove compartment / luggage bag.
I assume your question is about restoring the trip. Thus, you select one ticket after another randomly from this pile of tickets.
We assume that a bunch of tickets are of an undetermined size.
tak mnx cda bom 0 daj 0 phi 0
Where 0 value indicates unordered tickets. Let's define an unordered ticket as a ticket, where its dst does not match the src of another ticket.
The next next ticket discovers that mnx (dst) = kul (src) matches.
tak mnx cda kul bom 0 daj 1 phi 0 mnx 0
At any time you choose the next ticket, it is likely that it connects two consecutive airports. If this happens, you will create a node cluster of these two nodes:
<bom,tak>, <daj,<mnx,kul>>
and the matrix decreases,
tak cda kul bom 0 daj L1 phi 0
Where
L1 = <daj,<mnx,kul>>
which is a sublist of the main list.
Keep choosing the next random tickets.
tak cda kul svn xml phi bom 0 daj L1 phi 0 olm 0 jdk 0 klm 0
Match either existent.dst with new.src
or existent.src in new.dst:
tak cda kul svn xml bom 0 daj L1 olm 0 jdk 0 klm L2 <bom,tak>, <daj,<mnx,kul>>, <<klm,phi>, cda>
The above topological exercise is for visual understanding only. The following is an algorithmic solution.
The concept is to cluster ordered pairs in the lists to reduce the load on the hash structures that we will use to place tickets. Gradually there will be more and more pseudo-tickets (formed from united agreed tickets), each of which contains a growing list of ordered destinations. Finally, there will be one pseudo-ticket in his sublist containing the full route vector.
As you can see, perhaps this is best done with Lisp.
However, as an exercise related lists and maps ...
Create the following structures:
class Ticket:MapEntry<src, Vector<dst> >{ src, dst Vector<dst> dstVec; // sublist of mergers //constructor Ticket(src,dst){ this.src=src; this.dst=dst; this.dstVec.append(dst); } } class TicketHash<x>{ x -> TicketMapEntry; void add(Ticket t){ super.put(tx, t); } }
So, effectively,
TicketHash<src>{ src -> TicketMapEntry; void add(Ticket t){ super.put(t.src, t); } } TicketHash<dst>{ dst -> TicketMapEntry; void add(Ticket t){ super.put(t.dst, t); } } TicketHash<dst> mapbyDst = hash of map entries(dst->Ticket), key=dst TicketHash<src> mapbySrc = hash of map entries(src->Ticket), key=src
When a ticket accidentally gets out of a heap,
void pickTicket(Ticket t){ // does t.dst exist in mapbyDst? // ie attempt to match src of next ticket to dst of an existent ticket. Ticket zt = dstExists(t); // check if the merged ticket also matches the other end. if(zt!=null) t = zt; // attempt to match dst of next ticket to src of an existent ticket. if (srcExists(t)!=null) return; // otherwise if unmatched either way, add the new ticket else { // Add t.dst to list of existing dst mapbyDst.add(t); mapbySrc.add(t); } }
Check for existing dst:
Ticket dstExists(Ticket t){ // find existing ticket whose dst matches t.src Ticket zt = mapbyDst.getEntry(t.src); if (zt==null) return false; //no match // an ordered pair is matched... //Merge new ticket into existent ticket //retain existent ticket and discard new ticket. Ticket xt = mapbySrc.getEntry(t.src); //append sublist of new ticket to sublist of existent ticket xt.srcVec.join(t.srcVec); // join the two linked lists. // remove the matched dst ticket from mapbyDst mapbyDst.remove(zt); // replace it with the merged ticket from mapbySrc mapbyDst.add(zt); return zt; } Ticket srcExists(Ticket t){ // find existing ticket whose dst matches t.src Ticket zt = mapbySrc.getEntry(t.dst); if (zt==null) return false; //no match // an ordered pair is matched... //Merge new ticket into existent ticket //retain existent ticket and discard new ticket. Ticket xt = mapbyDst.getEntry(t.dst); //append sublist of new ticket to sublist of existent ticket xt.srcVec.join(t.srcVec); // join the two linked lists. // remove the matched dst ticket from mapbyDst mapbySrc.remove(zt); // replace it with the merged ticket from mapbySrc mapbySrc.add(zt); return zt; }
Check for existing src:
Ticket srcExists(Ticket t){ // find existing ticket whose src matches t.dst Ticket zt = mapbySrc.getEntry(t.dst); if (zt == null) return null; // if an ordered pair is matched // remove the dst from mapbyDst mapbySrc.remove(zt); //Merge new ticket into existent ticket //reinsert existent ticket and discard new ticket. mapbySrc.getEntry(zt); //append sublist of new ticket to sublist of existent ticket zt.srcVec.append(t.srcVec); return zt; }
I have the feeling that the above has some typos, but the concept should be correct. Any typo found, someone can fix it, plsss.