Hello everyone，we start to learn the Data Structures and Algorithms courses.
In this section,we firstly introduce a very important concept in Data Structures and Algorithms, that is problem solving.
Data Structures and Algorithms mainly focus on problem solving.
Firstly, what is the purpose of writing computer programs?
Our goal is to solve some problems that occurs in daily life or school life.
How to express this problem ?
Generally speaking, we'll give you some data input,then results can be got after the processing of your program.
How to describe the problem?
We need a data structure to describe the relationship between data of this problem.
After getting the data struture,which is also mathematical model, we can use corresponding algorithms to process the data appropriately and finally get an answer.
That is the process of transforming from question to data then to algorithm.
The programming is implemented by the interaction between data structure and algorithms.
In other words, algorithms can be included in the definition of data.
For example, in the description of Object-Oriented programming ,methods of how to process data can be implemented by using member function in object.
Our data structure can not be separated from data structure as well.
Data structure consists of logic、storage and operation.
In fact, the operation can be seen as the algorithms.
We look at an example and use it to understand the whole process of problem solving.
The farmer accross the river problem is described as below:
At first, one bank of the river is empty while there are three things on the other side of the bank, that is a wolf,a sheep and some vegetables.
The farmer rows a boat, and the boat can load one thing at one point, the farmer is not included of course.
The farmer takes one thing to across the river and then returns.
He can take one thing back or returns with an empty boat.
The farmer constraints these three things.
It means that, these things remains safe altogether while the farmer is beside. But when the farmer is not beside, wolf can not stay with the sheep and the sheep can not stay with the vegetables.
We need to describe all the constraints of the problem to describe it.
Then how to describe the data structure?
We can stand in the view of the original bank to think about this problem.
It means the status of the original bank will be changed from farmer,sheep,wolf,vegetables to empty.
That is to say, all the things are transfered successfully to the opposite side of the original bank include the farmer.
In the process of transfering, the statuses of the two banks will be changed, then which statuses are reasonable?
There is a constraint that wolf and sheep can not stay alone, as well as sheep and vegetables.
The complementary set of it is that the farmer can not stay alone with the vegetables, as well as the farmer and the wolf.
On the other hand, sheep,wolf and vegetables can not stay together without the farmer beside.
Six unreasonable status can be got then.
Besides, there are initial-state and end-state, the other statuses are reasonable.
Ten statuses are finally got at last. And how are these ten statuses associate with each other?
The statuses are associated by the transferring of the farmer or the famerr rows the empty boat to come and return.
So every time the farmer across the river reasonably, these statuses are associated.
For example, for the original status,if the farmer transfer the sheep to the opposite side of the bank, then wolf and vegetables are left.
Then the farmer rows the empty boat back, the status of the original bank is changed to farmer,wolf and vegetables, that is reasonable too.
All the reasonable transferring can be seen as the connection of the corresponding nodes.
We connect the lines with deep colour, and get the answer of this problem.
It means the farmer,sheep,wolf and vegetables is the initial-state.
Then the farmer takes the sheep to the opposite side of the bank, with the wolf and vegetables left.
Then the farmer rows the empty boat back, and the status of the original bank is changed to farmer,wolf and vegetables.
Then the farmer takes the wolf with him, and takes the sheep back, then the status of the original bank is changed to farmer,shhep and vegetables.
Then the vegetables are taken to the opposite side of the bank, then the status of the opposite bank is changed to farmer,wolf and vegetables.
The farmer then comes back and transfer the sheep and finally finish the work of transferring.
Our data structure can be described by an adjacent matrix.
All the reasonable nodes can be seen as position of one column or one row of the matrix.
The position between one row and one column means that a correlation happens between two statuses.
For example,accoring to the sequential number we arranged here, it is the first node.
Farmer,wolf,sheep and vegetables is the first node, while wolf and vegetables is the sixth node, there is an edge between them.
Accordingly, there is a value one in the sixth row of the first column.
If there is no association, the value will be zero.
In that way, we build a data structure.
The data structure can be expressed very well in the memory of our computer.
Then we'll try to find solutions for the data structure.
The process is to find an accessible path of the graph structure from the initial-state to the end-state.
In the data structures of computer, we mostly concerns about finding the best solution, that is to find the shortest path.
In the section of graph, we'll introduce the algorithm of Dijkstra to figure it out, so it will not be introduced here.
We introduce this example mainly to show you when a problem comes about, how to analyse the problem and construct a reasonable data structure to describe the association between data of the problem.
Then we find a classical algorithm or we redesign an appropriate algorithm to solve the problem and programming implementation is the final part of the process.
Your can think about what are the process of the Problem Abstration,Data Abstraction and Algorithm Abstraction?
Besides, if you analyse one problem in different ways, you may get different data structures.
Different algorithms will be needed accordingly.
You can also think about if there are some other solution for the farmer across the river problem.
Thank you!