Thuật giải – Bài tập lớn – Bài toán tìm đường đi trên bản đồ

Thuật giải – Bài tập lớn – Bài toán tìm đường đi trên bản đồ

Bài viết này của tôi nằm trong series ‘các bài tập tham khảo’. Series này chia sẻ một số cách tiếp cận, hiện thực mức căn bản nhất, tóm tắt nhất các bài tập, bài tập lớn ngành Khoa học máy tính, trường ĐH Mở Tp.HCM. Tôi hy vọng sẽ hữu ích với các bạn sinh viên IT đang chập chững trong học tập.

 

1.      GIới thiệu

Kì này, tôi sẽ giới thiệu một bài tập lớn của môn “thuật giải”: “Bài toán tìm đường đi trên bản đồ”. Ở ĐH Mở Tp.HCM, thì thường chúng ta sẽ học môn này vào năm 2.

Nếu như bạn muốn làm theo bài viết này của tôi thì tôi khuyên bạn hãy đọc thoáng qua rồi hãy bắt đầu. Đây không phải là một step by step tut.

Phạm vi tôi sẽ thực hiện:

–          Demo được bài toán tìm đường đi ngắn nhất trên chương trình có giao diện.

–          Dữ liệu trên bản đồ được chuẩn bị sẵn: kích thước 406×406 ,  5 điểm đi/đến.

Giao diện kết quả chương trình:

Một số kiến thức tôi sẽ áp dụng:

–          Lập trình WPF (Windows Presentation Foudation) <.NET 4.0 trở lên>

–          Ngôn ngữ lập trình C#

–          Giải thuật Dijkstra

Các bạn có thể sử dụng Windows Form, các hàm thư viện có khác nhau tí.

 

2.      Thiết kế chương trình

Xây dựng theo hướng chức năng:

–          Hiển thị các điểm có thể đi/đến lên combobox đi/đến

–          Chọn từ combobox đi/đến sẽ cập nhật lại điểm đầu/cuối, đường đi trên bản đồ.

Thiết kế dữ liệu và chuẩn bị tài nguyên:

Điểm, đường đi trên bản đồ sẽ được mô hình hóa bằng đỉnh và cạnh trong lý thuyết đồ thị. Lưu ý thêm là điểm (có thể chọn được) trên bản đồ chính là tập con của đỉnh trên đồ thị có hướng.

Dữ liệu đồ thị gồm 1 file text với cấu trúc:

[số_đỉnh]

[số_đỉnh_kề_với_đỉnh_0] [đỉnh_kề_thứ_0] [trọng_số] .. [đỉnh_kề_thứ_n] [trọng_số] [tên_đỉnh] [tọa_độ_x] [tọa_độ_y]

..

Xem ví dụ cho dễ hiểu:

8

1 1 43 _ 388 328

2 0 43 2 65 Bệnh_viện_Nguyễn_Tri_Phương 390 288

2 1 65 3 52 _ 389 229

3 2 52 5 162 7 110 _ 378 180

1 2 77 Công_viên_văn_lang 318 243

2 4 77 6 54 Nhà_thiếu_nhi_Quận_5 236 253

2 5 44 7 184 Trường_THCS_Chu_Văn_An 252 218

2 3 110 6 184 Vòng_xoay_Nguyễn_Tri_Phương 358 72

Số 8 đầu tiên có ý nghĩa là 8 đỉnh và bên dưới sẽ có 8 dòng (đánh số từ 0..7) . Dòng tiếp theo muốn nói là: đỉnh thứ 0 sẽ có 1 đỉnh kề. Chính là kề với đỉnh thứ 1 với trọng số là 43; tên là “_”; có tọa độ trên bản đồ tài nguyên là (388,328) . . .

Trọng số trong file text được tôi sử dụng chính là khoảng cách giữa 2 đỉnh trên bản đồ tài nguyên.  Thực tế trọng số các bản đồ xịn không chỉ được quyết định nhờ vào khoảng cách mà còn có thể từ địa hình cao thấp, tình trạng giao thông,…

Các tên đỉnh sử dụng “_” thay cho khoảng trắng vì mục đích đơn giản hóa quá trình nhập.

Tại sao không xây dựng một công cụ nhập đỉnh trực quan? Dĩ nhiên chúng ta có thể xây dựng công cụ đó và tích hợp vào chương trình chúng ta. Nhưng trong phạm vi bài viết này, tôi đã giới hạn từ đầu là sẽ chỉ demo giải thuật.

Còn việc load một map xịn như Google Map, map còn có cả dịch vụ tìm đường? Bài viết này hoàn toàn hướng đến việc chúng ta học tập kiến thức nền tảng lập trình, thuật toán… nên chúng ta sẽ tự cài đặt chức năng tìm đường. Ở đây, tôi chỉ mới cắt một phần bản đồ rất nhỏ trong OpenStreetMap (một dịch vụ bản đồ số miễn phí).

 

3.      Thiết kế giao diện:

WPF cung cấp cách thức xây dựng giao diện linh hoạt bằng XAML. Đây là file giao diện.

  
<Window x:Class="MyDigiMap.MainWindow"
        xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
        xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
        Title="My DigiMap" Height="440" Width="420" >
    <Grid>
        <Grid.ColumnDefinitions>
            <ColumnDefinition Width="406" />
        </Grid.ColumnDefinitions>
        
        <Canvas Grid.Column="0" Name="cnvMain">
            <Image Source="Resources/openStreetMap.jpg"></Image>
            <Path Name="patDirection" Stroke="Firebrick" StrokeThickness="3" ></Path>
            <Ellipse Name="elpBegin" Canvas.Left="-50" Width="16" Height="16" Fill="Lime" Stroke="Green" StrokeThickness="2"></Ellipse>
            <Ellipse Name="elpEnd" Canvas.Left="-50" Width="16" Height="16" Fill="Yellow" Stroke="OrangeRed" StrokeThickness="2"></Ellipse>
            <StackPanel Width="200" Canvas.Bottom="10" Canvas.Left="10" Background="Black" Opacity="0.7">
                <StackPanel Orientation="Vertical" Margin="5">
                    <StackPanel Orientation="Horizontal">
                        <Label Background="Lime" BorderThickness="1" BorderBrush="Green"></Label>
                        <Label Foreground="White">Từ  :</Label>
                    </StackPanel>
                    <ComboBox Name="cboBegin"></ComboBox>
                </StackPanel>
                <StackPanel Orientation="Vertical" Margin="5">
                    <StackPanel Orientation="Horizontal">
                        <Label Background="Yellow" BorderThickness="1" BorderBrush="OrangeRed"></Label>
                        <Label Foreground="White">Đến :</Label>
                    </StackPanel>
                    <ComboBox Name="cboEnd"></ComboBox>
                </StackPanel>
            </StackPanel>
        </Canvas>

    </Grid>
</Window>

Design View:

 

Một số bạn đã tìm hiểu qua về WPF sẽ nghĩ đến vấn đề sử dụng kiến trúc MVVM. Nhưng ở đây, tôi muốn source code thật dễ hiểu như học “lập trình giao diện” nên tôi bỏ qua MVVM.

 

4.      Lập trình:

a.       Đọc dữ liệu

Đầu tiên để đọc dữ liệu từ file text và ghi vào bộ nhớ. Tôi khai báo một số biến thành viên của lớp MainWindow

  
        private int _vertexNumber; //số đỉnh
        private string[] _vertexName; //tên các đỉnh
        private double[,] _graphMatrix; //ma trận kề
        private List<int>[] _graphList; //danh sách kề
        private Point[] _vertexPosition; //tọa độ các đỉnh

Khi window load lên, tôi gọi hàm đọc dữ liệu. Đầu vào của hàm là file text dữ liệu mình đã chuẩn bị. Chỉ cần với một số kĩ năng làm việc với file và chuỗi thì chúng ta nhanh chóng hoàn thành được bước này. Source code hàm đọc dữ liệu:

         
        private void InputGraphFromFile(string fileUrl)
        {
            TextReader textReader = new StreamReader(fileUrl);
            _vertexNumber = int.Parse(textReader.ReadLine());
            _vertexName = new string[_vertexNumber];
            _graphList = new List<int>[_vertexNumber];
            _graphMatrix = new double[_vertexNumber,_vertexNumber];
            _vertexPosition = new Point[_vertexNumber];
            int i, j, k, n;
            double w;
            string[] buffStringArray;
            for (i = 0; i < _vertexNumber; ++i)
                for(j=0;j<_vertexNumber; ++j)
                    if (i == j)
                        _graphMatrix[i,j] = 0;
                    else
                        _graphMatrix[i,j] = MaxWeight;

            for (i = 0; i < _vertexNumber; ++i)
            { 
                buffStringArray = textReader.ReadLine().Split(' ');
                n = int.Parse(buffStringArray[0]);
                _graphList[i] = new List<int>();
                for(j=0;j<n;++j)
                {
                    k = int.Parse(buffStringArray[j * 2 + 1]); //mỗi đỉnh kề của đỉnh i
                    w = double.Parse(buffStringArray[j * 2 + 2]); //trọng số đính kèm từ đỉnh i đến đỉnh k
                    _graphList[i].Add(k);
                    _graphMatrix[i, k] = w;
                }
                _vertexName[i] = buffStringArray[n * 2 + 1]; //tên đỉnh
                _vertexPosition[i].X = double.Parse(buffStringArray[n * 2 + 2]); //tọa độ x
                _vertexPosition[i].Y = double.Parse(buffStringArray[n * 2 + 3]); //tọa độ y
            }
            textReader.Close();
        }

Thông thường để hiện thực đồ thị, chúng ta hay sử dụng cấu trúc dữ liệu là ma trận kề hoặc danh sách kề. Tuy nhiên, lí do gì tôi lại chấp nhận dư thừa, lưu vào cả 2 biến: _graphMatrix và _graphList? Tôi sẽ giải thích ngay sau đây.

 

b.       Tìm đường đi ngắn nhất bằng giải thuật Dijkstra

Ý tưởng thu gọn:

Lấy đỉnh gần “đỉnh đi” nhất, nếu đỉnh đó là “đỉnh đến” thì đã tìm thấy đường đi ngắn nhất, ngược lại sẽ xét đỉnh gần nhất đó với toàn bộ các đỉnh khác xem nếu đi đến “đỉnh gần nhất đó” rồi mới đến “đỉnh đang xét” thì có nhanh hơn không? Nếu nhanh thì sau này sẽ đi bằng đường đó. Xét toàn bộ xong thì lại quay về lấy đỉnh gần “đỉnh đi” nhất như trên đến khi đỉnh gần nhất là “đỉnh đến”.

Trên internet có khá nhiều mã giả, cách tối ưu thời gian chạy… Nhưng ở đây, tôi làm đơn giản nhất. HIện thực bằng 2 hàm sau:

–          Dijkstra nhận vào số thứ tự đỉnh đi và đến. trả ra tổng trọng số đường đi ngắn nhất. đồng thời thể hiện các đỉnh trên đường đi trên mảng parent.

–          GetVertexPath nhận vào số thứ tự đỉnh đi, đến, mảng parent đã tính từ Dijkstra trước đó. Trả về 1 danh sách số thứ tự các đỉnh trên đường đi.

    
        int[] _parent; //kết quả dijkstra : parent[i] là đỉnh trước của đỉnh i

        private const double MaxWeight = 100000;
        private double Dijkstra(int start, int end, ref int[] parent)
        {
            double[] distance = new double[_vertexNumber + 1];
            parent = new int[_vertexNumber];
            bool[] visited = new bool[_vertexNumber];
            int i, j, k;
            for(i=0;i<_vertexNumber;++i)
            {
                distance[i] = _graphMatrix[start,i];
                parent[i] = start;
                visited[i] = false;
            }
            visited[start] = true;
            distance[start] = MaxWeight;
            distance[_vertexNumber] = MaxWeight;
            while (true)
            {
                var min = _vertexNumber;
                for (i = _vertexNumber-1; i >= 0; --i)
                    if (visited[i] == false && distance[i] < distance[min])
                        min = i;
                if (min == _vertexNumber)
                    break;
                if (min == end)
                    break;
                var v = min;
                visited[v] = true;
                foreach (var u in _graphList[v])
	            {
                    var sum =  distance[v] + _graphMatrix[v,u];
                    if (visited[u] == false && distance[u] > sum)
                    {
                        distance[u] = sum;
                        parent[u] = v;
                    }
	            }
            }
            return distance[end];
        }

        private List<int> GetVertexPath(int start, int end, int[] parent)
        {
            List<int> result = new List<int>();
            int temp = end;
            while (temp != start)
            {
                result.Add(temp);
                temp = parent[temp];
            }
            result.Add(temp);
            result.Reverse();
            return result;
        }      

Nhằm tránh phép cộng gây tràn số, hằng số MaxWeight để quy định trọng số tối đa thay cho double.Max.

 

c.       Cài đặt nguồn dữ liệu và sự kiện mỗi khi chọn 1 giá trị trên 2 combobox

  
        int _startVertex; //đỉnh đi
        int _endVertex; //đỉnh đến
        private void InitInputComboboxSourceAndEvent()
        {
            var userVertex = _vertexName
                .Select((name, index) => new { VertexIndex = index, Name = name})
                .Where(p => p.Name != "_")
                .Select(name => new { VertexIndex = name.VertexIndex, Name = name.Name.Replace('_', ' ') });
            cboBegin.ItemsSource = userVertex;
            cboBegin.DisplayMemberPath = "Name";
            cboEnd.ItemsSource = userVertex;
            cboEnd.DisplayMemberPath = "Name";
            var descriptor = DependencyPropertyDescriptor.FromProperty(ComboBox.TextProperty, typeof(ComboBox));
            //khi chọn 1 item sẽ cập nhật lại _startVertex
            descriptor.AddValueChanged(cboBegin, delegate
            {
                if (cboBegin.SelectedIndex != -1)
                {
                    _startVertex = ((dynamic)cboBegin.SelectedItem).VertexIndex; 
                    DrawVertex(elpBegin, _startVertex);
                    DrawPath();
                }
            });
            //khi chọn 1 item sẽ cập nhật lại _endVertex
            descriptor.AddValueChanged(cboEnd, delegate
            { 
                if (cboEnd.SelectedIndex != -1)
                {
                    _endVertex = ((dynamic)cboEnd.SelectedItem).VertexIndex;
                    DrawVertex(elpEnd, _endVertex);
                    DrawPath();
                }
            });
        }        

Nguồn dữ liệu cho 2 combobox là điểm đi/đến, tức là các đỉnh có tên không phải là “_” . 1 dòng lựa chọn trong 1 combobox phải cho chúng ta biết được tên và số thứ tự của đỉnh. Vì vậy bắt buộc phải lưu cả 2 giá trị chứ không thể tận dụng thứ tự trong control combobox. Buộc ta phải xây dựng một lớp thêm có 2 thuộc tính. Nhưng vì lớp có tần suất sử dụng ít nên tôi quyết định sử dụng anonymous type để có thể dễ dàng quản lý cục bộ. Kết hợp giải pháp LINQ sẽ giúp việc trích lọc ngắn gọn trong vài dòng code.

Sự kiện thay đổi lựa chọn của WPF có hơi phần khác với Windows Form. Nếu sử dụng sự kiện SelectionChanged thì chỉ có thể lấy được lựa chọn trước khi thay đổi thôi. Cách giải quyết là thiết lập cho combobox có khả năng AddValueChanged thông qua đối tượng DependencyPropertyDescriptor .Trong mỗi anonymous methods được gắn, số thứ tự đỉnh được lấy ra. Nguồn dữ liệu trong combobox là kiểu anonymous nên ta cần ép về kiểu dynamic để truy xuất thuộc tính.

DrawVertex là hàm hiển thị điểm đi/đến. Đầu vào là control ellipse đại diện cho điểm đi/đến. Tham số kế tiếp là số thứ tự đỉnh đang được chọn:

          
        private void DrawVertex(Ellipse element, int v)
        {
            Canvas.SetLeft(element, _vertexPosition[v].X - element.Width/2);
            Canvas.SetTop(element, _vertexPosition[v].Y - element.Height/2);
        }

Còn hàm DrawPath sẽ vẽ đường đi giữa 2 điểm trên bản đồ (chỉ khi 2 điểm được chọn đủ). Trong DrawPath, gọi hàm Dijkstra để chạy thuật toán tìm đường đi và GetVertexPath để trả về mảng thứ tự các đỉnh trên đường đi. Từ mảng đó lấy các tọa độ tương ứng đưa vào một số đối tượng đồ họa. Cuối cùng sẽ tạo được một đối tượng của lớp PathGeometry gắn vào Data của Path.

   
        private void DrawPath()
        {
            if (cboBegin.SelectedIndex != -1 && cboEnd.SelectedIndex != -1)
            { 
                var minDistance = Dijkstra(_startVertex, _endVertex);
                var minPath = GetVertexPath(_startVertex, _endVertex);
                var pathSegmentCollection = new PathSegmentCollection();
                var pathFigure = new PathFigure() { 
                    StartPoint = _vertexPosition[minPath[0]], 
                    Segments = pathSegmentCollection 
                };
                for (int i = 0; i < minPath.Count; i++)
                    pathSegmentCollection.Add(new LineSegment(_vertexPosition[minPath[i]], true));

                var pathFigureCollection = new PathFigureCollection();
                pathFigureCollection.Add(pathFigure);
                var pathGeo = new PathGeometry(pathFigureCollection);
                patDirection.Data = pathGeo;
            }
        }      

d.       Phương thức thiết lập

Cuối cùng, trong phương thức thiết lập của window gọi các hàm để gắn kết toàn bộ chương trình:

         
        private const string _fileUrl = "Resources/mapdata.txt";
        public MainWindow()
        {
            InitializeComponent();
            InputGraphFromFile(_fileUrl);
            InitInputComboboxSourceAndEvent();
        }

Hình ảnh minh họa đây là đồ thị có hướng: A->B và B->A có đường đi khác nhau.

Bài viết đến đây là hết. Cám ơn các bạn đã quan tâm. Rất vui nhận được góp ý của các bạn